I have written a CFG that supposedly generates $L$ below.

$$L = \{w \in \{a, b\}^* \text{ }| \text{ } w \text{ has } n_a(w) = 2n_b(w)\}$$

Where $n_a(w)$ is the number of $a$'s in $w$ and similarly for $n_b(w)$.

My reasoning is that for every $b$ in $w \in L$, we will be able to pair it up with two distinct $a's$ in $w$. There are $3$ distinct orders in which this triple can occur in $w$, namely: $(a, a, b)$, $(a, b, a)$ and $(b, a, a)$. Thus my grammar is as follows.

$$S \rightarrow SaSaSbS \text{ }|\text{ } SaSbSaS \text{ }|\text{ } SbSaSaS \text{ }| \text{ } \epsilon$$

By placing the variable $S$ in between, I am attempting not to make any assumptions about the position of the triple in $w$, only the relative position amongst the triple's elements.

From other questions discussing this $L$, I can see that my grammar is much uglier, but as far as I can tell it seems correct. Are there any strings in $L$ that it cannot generate?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.