Peter Linz Exercise 5.1

Question

Give a context-free grammar for the language below :

(n>=0, m>=0)

L= { w ∊ {a,b}^* : n_a(w)=2n_b(w)+1}

Answer 1

$$\begin{align*} &S\rightarrow aA\;|\;Aa \\ &A\rightarrow aAbAa\;|\;aaAb\;|\;bAaa\;|\;AA\;|\;\epsilon \end{align*}$$

Comments

Could you please explain the base case of this solution?

---

Hello, I was wondering if you ever found out the solution to this problem?

---

This solution is not correct since the string baaaaab is not derived here.

---

the strings starting and ending with b can never be achieved

 

Answer 2

I think it will work for all cases

$S\rightarrow aA|Aa|AaA$

$A\rightarrow \varepsilon |aaAb|bAaa|aAbAa$