Question

In: Computer Science

Prove that {anbamba2m+n:n,m≥1} is not regular using pumping lemma

Prove that {anbamba2m+n:n,m≥1} is not regular using pumping lemma

Solutions

Expert Solution

To prove that is not regular, use the pumping lemma for regular languages as follows.

Let the pumping length be . Consider the word which has length at least p, which is in the language as per the definition of the language with .

Consider any breakup of the word . Then xy must consist of only 'a's from the first block, otherwise it's length will exceed p. Hence . Now consider the pumped down word . Then this word has , but the number of 'a's in the last block is . As , this means , hence . This means that the word w' doesn't satisfy the property to be in the language, hence .

This proves the language is not regular using the pumping lemma for regular language. Comment in case of any doubts.

venereology answered 4 hours ago
Next > < Previous

Related Solutions

1. Pumping Lemma: a. Is the following language a regular language? (Use pumping lemma in proof.)...
1. Pumping Lemma: a. Is the following language a regular language? (Use pumping lemma in proof.) L = {0n 1n 2n | n ≥ 0} b. What is (i.e., define) the CFL pumping lemma?
Using the pumping lemma, prove that the language {1^n | n is a prime number} is...
Using the pumping lemma, prove that the language {1^n | n is a prime number} is not regular.
Do not use Pumping Lemma for Regular Expression to prove the following. You may think of...
Do not use Pumping Lemma for Regular Expression to prove the following. You may think of Closure Properties of Regular Languages 1. Fix an alphabet. For any string w with |w| ≥ 2, let middle(w) be the string obtained by removing the first and last symbols of w. That is, Given L, a regular language on Σ, prove that f1(L) is regular, where f1(L) = {w : middle(w) ∈ L}
Use the pumping lemma to show that the following languages are not regular. A a. A1={0^n...
Use the pumping lemma to show that the following languages are not regular. A a. A1={0^n 1^n 2^n | n≥0} b. A2 = {www | w ∈ {a,b}∗} A c. A3 ={a^2^n | n≥0} (Here, a^2^n means a string of 2^n a’s.) A ={a3n |n > 0 }
Use the pumping lemma to show that the following languages are not regular (c) (5 pts)...
Use the pumping lemma to show that the following languages are not regular (c) (5 pts) Let Σ = {0, 1, −, =} and SUB = {x = y − z | x, y, z are binary integers, and x is the result of the subtraction of z from y}. For example: 1 = 1 − 0, 10 = 11 − 01 are strings in SUB but not 1 = 1 − 1 or 11 = 11 − 10.
Show that L2 = {anb2nan : n ≥ 0} is not context-free using the pumping lemma.
Show that L2 = {anb2nan : n ≥ 0} is not context-free using the pumping lemma.
Using Euclid's Propositions: 1. Prove that the regular octagon is constructible. 2. Prove that the regular...
Using Euclid's Propositions: 1. Prove that the regular octagon is constructible. 2. Prove that the regular decagon is constructible.
Prove that √3 is irrational using contradiction. You can use problem 4 as a lemma for...
Prove that √3 is irrational using contradiction. You can use problem 4 as a lemma for this. Problem 4, for context is Prove that if n2 is divisible by 3, then n is divisible by 3.
prove using limit lemma that n^2 > nlogn given some epsilon > 0
prove using limit lemma that n^2 > nlogn given some epsilon > 0
let sigma = {a,b,c}. Use the Pumping Lemma to show that the language L defined below...
let sigma = {a,b,c}. Use the Pumping Lemma to show that the language L defined below is not regular. L={ a^p c(bb)^q : q > p >1}
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT