Peter Linz Edition 4 Exercise 1.2 Question 18 (Page No. 29)

Question

Assume $\sum = \left \{ a,b \right \}$ 

1. $L = \left \{ w : n_{a}\left ( w \right ) = n_{b}\left ( w \right ) + 1 \right \}$
2. $L = \left \{ w : n_{a}\left ( w \right ) > n_{b}\left ( w \right ) \right \}$
3. $L = \left \{ w : n_{a}\left ( w \right ) = 2n_{b}\left ( w \right ) \right \}$
4. $L = \left \{ w \in \left \{ a,b \right \}^{*} : \left |n_{a}\left ( w \right ) - n_{b}\left ( w \right ) \right | = 1 \right \}$

Comments

All are $DCFL.$

---

ok but grammars? atleast for (1)

Answer 1

1) S -> aX / XS

  X -> XX / aXb / bXa / $\epsilon$ ( Thanks  @Tarun kushwaha 1 )

2) S-> aSb | bSa | SS |A

     A-> aA | a

3) S-> aaSb | bSaa |aSba|abSa|SS|ε (thanks @srestha)

4)S -> aX | bX | XS

  X -> aXb | bXa | XX |ε

Comments

not able to generate aba from 3rd one

---

it will be

S-> aaSb | bSaa |aSba|abSa|SS|ε

---

@tesla

typing mistake in the line

3) S-> aaSb | bSaa |SS|aSba|abSaε

Answer 2

Grammar for 1st..

S --> aX / XS

X --> XX / aXb / bXa / λ

Answer 3

are the following grammars correct ?

1.     S-> aA / Aa

        A -> aAbA / bAaA / ϵ

2.    S -> aSbS / bSaS / aS / a

3.    S -> aaSbS / bSaaS /  ϵ

4.    S -> aSbS / bSaS / a /b

Comments

not able to generate aba from 3rd one

---

yes i missed that. Thankyou.

---

and not able to generate abbaaa from 2nd one