The Gateway to Computer Science Excellence
+2 votes
169 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.??

in Theory of Computation by Veteran (57k points)
retagged by | 169 views
0
typo..fixed

1 Answer

+3 votes
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.
by Veteran (117k points)
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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,473 answers
195,393 comments
100,370 users