Pumping Lemma

Assume L be a ordinary language.

Then, there is an integer n≥0 so that for every string x in L that |x|≥n, there are strings u, v, and w so that

-   x = u v w,

-   v ≠ e,

-   |u v| ≤ n, and

-   for all k ≥ 0, u vk w is also in L

Language L is not a regular language if for any integer n≥0 , there is a string x in L so that |x|≥n, for any strings u, v, and w,

-   x ≠ u v w, or

-   v = ε, or

-   Not (|u v| ≤ n), or

-   there is k≥ 0, u vk w is not in L

Language L is not a regular language if

• for any integer n ≥ 0 ,
• there is a string x in L so that |x| ≥ n,
• for any strings u, v and w, so that x = u v w, v≠ε, and |u v| ≤ n,

-   there is k ≥ 0, u vk w is not in L

• Given a language L.
• Assume n is any integer ≥ 0 .
• Choose a string x in L such that |x| ≥ n.
• Consider all the possible ways to chop x into u, v and w that v≠ε, and |uv| ≤ n.
• For all the possible u, v, and w, show that there is k ≥ 0 that u vk w is not in L.
• We can conclude that L is not regular.

Email based Automata assignment help – homework help

The study of automata is an important area of theory of computation. Students feel trouble in solving automata questions. We at www.expertsmind.com offers Automata assignment help – Automata homework help and online tutoring with best qualified and experienced computer science tutor’s help. We cover all topics including Pumping Lemma in assignment help – homework help service. Get solved problems in automata theory with step by step answers anytime from expert tutors at expertsmind.