typo..fixed

The Gateway to Computer Science Excellence

+2 votes

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

+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.

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

0

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,473 answers

195,393 comments

100,370 users