Question

Consider the following languages Li and L2, respectively, and construct a context free grammar for it if it is a context free language; if not, using the pumping lemma to disprove it. Let na(w) denote the number if a is w, same notation for to now) and nc(w). • L1 = {w we {a,b}* and na(w) = nb(w)} • L2 = {w I w€ {a,b,c}* and na(w) = n5(w) = nc(w)}

Answer 1

4 ={w/ we {a,b3* and na (w)= nb (ew) } ų is a language over alphabet {a,by and no. of "äs = no. of b's in a string of the Given language. for this language, we have to count the number of a and b in a string. For this we require a stack to count a and to So, for this language L, Pushdown automata can be possible. Pushdown automata (finite automata & Stack) (6, 20/626) Ca, zo/azo) Cable) vocba/6) D (6,2012.) Y (a, alaa) (6 blaa) a, Zo/azo) when we see a as ilp and zo on the top of stack then Stack are push a. (a, b/El when we see a as ilp and bon the top of the stack, then pop. CSscanned with CamScanner

Pushdown automata for Language Ly is possible. So, ay is content of content free language. Content free grammar for. Ly: E={a, by VE { S, ,5} s aso lbsal s → ssle CScanned with CamScanner

BROODOO WAWA S8 L₂ = { w/wth a, b, Got and na(w)= (w) = 1. (W) } L2 is a language over alphabet {a,b,c} and na (w)2 n₂(W) 2 M. (W) ₂ is not a Context free language to because Push down automata is not possible for this language L2 and it is not possible to count the equal no of a, b, and c using stack. 500 is with the help of pumping Lemma, we have to prove that is not context free language:

pumping lemma for context free language It is a Context free language and WEL Such that Iwl on then 'W' can be decomposed as We axcye such that 0 xy + (16) 1x cylsn (1) For all '70, the String ax cyle is also For language La given above we take a string s= a aaabbbb cccc.. s will we decompose s' into 5 parts S= a(a ala bb bb cccc When we pump x and a then no of a, b and C are not equat it, saa a ala bb bb crgo When we pump x andy then also no of a, b and c are not equal So, tan string's' does not satisfy pumping lemma property so, language is not a context free language so Context free Grammar for L2 is not possible