context free grammar || Linz 5.1

Question

$\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.??

Comments

typo..fixed

Answer 1

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.

Comments

so 3 & 2 are wrong ?

---

if possible please provide 2/3 lines of explanation regarding third grammar..placing S specially . thanks !

---

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

---

thanks !!