Question

Use the pumping lemma for regular languages to prove that the following language is not regular....

Use the pumping lemma for regular languages to prove that the following language is not regular.

{ 0n1x0x1n | n >= 0 and x >= 0 }

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

Let us assume that L is a regular language. Let us assume that m = 0n1x0x1n belongs to L and u = 0n, v = 1x and w = 0x1n.

Clearly, |uv| <= n and |v| >= 1.

Now, for i = 2, uviw = 0n12x0x1n

Clearly, uv2w does not belong to L and hence, our assumption was wrong, This means that L is not regular.

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Prove that the following languages are not regular using pumping lemma: (a) {w : w !=...
Prove that the following languages are not regular using pumping lemma: (a) {w : w != wR} (b) {ai bjak : k ≤ i + j}
Use the pumping lemma to show that the following languages are not regular. b. A2 =...
Use the pumping lemma to show that the following languages are not regular. b. A2 = {www| w € {a, b}*}
Are the following languages over {a, b} regular? If they are then prove it. If they...
Are the following languages over {a, b} regular? If they are then prove it. If they are not prove it with the Pumping Lemma {an bm | m != n, n >= 0} {w | w contains the substring ‘aaa’ once and only once } Clear concise details please, if the language is regular, provide a DFA/NFA along with the regular expression. Thank you. Will +1
Test the language L2.16={(ab^n,n>0) with the pumping lemma and show that it is regular.
Test the language L2.16={(ab^n,n>0) with the pumping lemma and show that it is regular.
Prove the language of strings over {a, b} of the form (b^m)(a^n) , 0 ≤ m...
Prove the language of strings over {a, b} of the form (b^m)(a^n) , 0 ≤ m < n-2 isn’t regular. Use the pumping lemma for regular languages.
Use pumping lemma to prove that L3a = {ab^m ab^m a| m>0} is non-regular
Use pumping lemma to prove that L3a = {ab^m ab^m a| m>0} is non-regular
Using the pumping lemma for context free Languages to prove L is not context free. L...
Using the pumping lemma for context free Languages to prove L is not context free. L = { w#w#w | w E (0+1)*} Are the used variables {0,1,#}
Prove the language of strings over {a, b} of the form (b^m)(a^n) , 0 ≤ m...
Prove the language of strings over {a, b} of the form (b^m)(a^n) , 0 ≤ m < n-2 isn’t regular. (I'm using the ^ notation but your free to make yours bman instead of (b^m)(a^n) ) Use the pumping lemma for regular languages.
prove that the language L over {c,d,e} is not context free. (using pumping lemma for context...
prove that the language L over {c,d,e} is not context free. (using pumping lemma for context free languages) L= {w ∈ {c,d,e}* : number of c's, number of d's, and number of e's have a common factor greater than 1}
Prove that {anbamba2m+n:n,m≥1} is not regular using pumping lemma (5).
Prove that {anbamba2m+n:n,m≥1} is not regular using pumping lemma (5).
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT