search
Log In
2 votes
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.??

in Theory of Computation
retagged by
203 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.

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

0 votes
0 answers
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
asked Oct 18, 2018 in Theory of Computation Sambhrant Maurya 110 views
0 votes
1 answer
2
265 views
Do the following productions mean the same Bb->bb and B->b My doubt is that will the first production be used only when we have b in the follow of B or it can be used in any case. If it can be used in any case then will the first production be equal to second production.
asked Apr 4, 2017 in Theory of Computation Srinivas Rao 265 views
1 vote
1 answer
3
316 views
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*}$
asked Mar 25, 2017 in Theory of Computation gabbar 316 views
0 votes
0 answers
4
121 views
consider following grammer S → aSb / aSbb / aSbbb / ….. is language generated by above grammer is DCFL?
asked Dec 24, 2018 in Theory of Computation Rahul_Rathod_ 121 views
...