Pumping lemma: (a) Show that A = { w ? {a, b, c} ? | w has more a’s than b’s } i

Question

Pumping lemma:

(a) Show that A = { w ? {a, b, c} ? | w has more a’s than b’s } is not regular.

(b) Show that B = { w |w ? {a, b, c} ? , na(w)/nb(w) = nc(w)} is not context-free. (Here, na(w) means the number of a’s in w, similarly for nb(w) and nc(w).)

(c) Show that C = { a i 2 |i ? 0} is not context free

Pumping lemma: (a) Show that A w E ta, b, c w has more a's than b's is not regular (b) Show that B w lu E {a, b, no w (w) nc(w) is not context-free. (Here na (w means the number of a's in w, similarly for nb(w) and no w (c) Show that C a i 20) is not context free

Explanation / Answer

Solution for question a:

Suppose that A is a regular language.let p be the "pumping length" of Pumping Lemma.consider the string s=c^p b^p+1 a^p+2.note that s € A and |s|=3p+3 >=p,so the Pumping Lemma will hold.Thus we.can split the string s into 3 parts s=xyz satisfying conditions but c cannot be identified because here in condition there is no representation about c is equal.,not equal,greater or smaller

i xy^iz € A for I>=0,

ii |y|>0,

iii |xy|<=p

since first p symbols are all b's the third condition implies that C and y consist only of b's. So z wi be rest of b's followe by a ^p+2.the second condition states that |y| >0 so y has atleast one b.we can the. Say that x=b^j for some j>=0,y=b^k for some k>=1,z=b^ma^p+1 for some m>=0

sincd.b^p+1 a^p+2=s=xyz=b^jb^kb^ma^p+2=b^j+k+m a^p+2 ,we must have that j+k+m=p the first condition iimplies xy^2z €A but xy^2z=b^jb^kb^kb^ma^p+2. =b^p+k a^p+2

since j+k+m=p hence xy^2z€/ A because it doesn't have more a'show ththan b'show since.k>=1 anhow we get a contradiction.therefore A,is a non regularregular language.

Solution for question b:

If we tey to

S-> SS|aSc|cSa|bSc|€

Solution for questuion c:

C= { a i 2|i>=0 }. Suppose C= {a i 2|i>=0} were context free.then we could pump.Let i=M ^2.so w is the string with M.^2^2, or M^4,a's.) Clearly |w| >= K since M>K.so uvvxyyz must be in C(whatever v and u are).But it can't be.why not? Given our w,the next element of C is the string with (M^2 +1)^2 a's.That's M^4+2M^2+1(expanding it out).Bur we know that |vxy|<=M,so we can't pump in more than M a's when we pump only once.Thus the string we just created can't have more than M^4+M a's.Clearly not enough.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.