# context free grammar || Linz 5.1

203 views

\begin{align*} & L = \left \{ w \in \left \{ a,b \right \}^{*}\;\; : n_a(w) \neq n_b(w) \right \} \\ & S\rightarrow aSb|bSa|A|B \\ & A \rightarrow aA|a \\ & B \rightarrow bB|b \\ \hline \\ & L = \left \{ w \in \left \{ a,b \right \}^{*}\;\; : n_a(v) \geq n_b(v) \; \text{where } v \text{ is any prefix of } w \right \} \\ & S\rightarrow aSb|SS|A \\ & A \rightarrow aA|\epsilon \\ \hline \\ & L = \left \{ w \in \left \{ a,b \right \}^{*}\;\; : n_a(w) = 2.n_b(w) + 1 \right \} \\ & S\rightarrow aSbSa|aSaSb|bSaSa|SS|a \\ \end{align*}

Please verify all grammars. third grammar In Linz book it is given as

\begin{align*} & S\rightarrow aSbSa|aaSb|bSaa|SS|a \\ \end{align*} ..better explanation if possible.??

retagged
0
typo..fixed

For 3rd one

$S\rightarrow aaS_{1}b|aS_{1}ab|aS_{1}ba|abS_{1}a|bS_{1}aa|baS_{1}a$|SS

$S_{1}\rightarrow a$

It is very easy and correct grammer, if u see all it's combinations.

Their explanation is also correct. I just add some more steps for easy explanation.

Suppose , a grammar follows 3rd rule , what it includes?

$(aaab,aaaaabb,bbaaaaa, ...................)$

So, we can do grammar like this,$S\rightarrow aaSb$, where we can get any $a^{2n}b^{n}$ grammar. But we need $a^{2n+1}b^{n}$. For that odd 1, we add it at last in CFL.

edited by
0
so 3 & 2 are wrong ?
0
if possible please provide 2/3 lines of explanation regarding third grammar..placing S specially . thanks !
0
Placeing of S should be such that it includes all string.

$S\rightarrow aaSb|a$ Which includes aaab,aaaaabb............

$S\rightarrow bSaa|aaSb|a$

Which includes baaa,baaabaa,......................

Got now?

Now, 2 is correct
0
thanks !!

## Related questions

1
110 views
Consider the following CFG 'G' S--> aA/bSS/SS A--> aAb/bAa/AA/ε The language generated by G is: a)Set of all strings with atleast one 'a' b)Set of all strings with atleast two a's c)Set of all strings with atleast one more 'a' than number of b's d)None of these
Construct context-free grammars to accept the following languages. \begin{align*} \large L = \left \{ 0^i1^j2^k \;\; | \;\; i \neq j \;\; or \;\; j \neq k \right \} \end{align*}