State and explain pumping lemma for regular languages. Using pumping lemma prove that the language L={0^n 1^n

6.2kviews

State and explain pumping lemma for regular languages. Using pumping lemma prove that the language L={0^n 1^n | n>=0} is not regular.

written 8.7 years ago by

teamques10 ★ 70k

• modified 3.8 years ago

Mumbai University > Computer Engineering > Sem 4 > Theoretical Computer Science

Marks: 10M

Year: Dec 2016

theory of computation

ADD COMMENT EDIT

1 Answer

241views

written 8.7 years ago by

teamques10 ★ 70k

Pumping Lemma

Let L be a regular language and let Z be a word of L such that |z|>=n,

Where n is the minimum number of DFA states required for recognizing L, then we can write z=uvw

Where |uv|<=n and 1<=|v|<=n.

Such that all strings of the form

uv^iw for …

Create a free account to keep reading this post.

and 5 others joined a min ago.

ADD COMMENT EDIT

Please log in to add an answer.