I'm trying to prove that the language L generated by the CFG $S \to aS | aSbS | \varepsilon$ is the language $L=\{ w \in \{a,b\}^*: \text{every prefix of $w$ has at least as many $a$'s as $b$'s} \}$.I proved the first inclusion $w \in L(G) \implies w \in L$. I can't prove the vice versa. By induction on the lenght of $w \in L$, I could say:

BASE: $|w|=0$, i.e. $w=\varepsilon$ and it's clear.

IND: suppose the thesis is true whenever $|w|<n+1$ and prove for a word of lenght $n+1$. Given $w \in L$, $w=a_1\dots a_{n+1}$ one has $a_1=a$ since $a_1$ is a prefix of $w$. Thus I can first apply the rule $S \to aS$ or $S \to aSbS$. But what now?

Any suggestion would be helpful. Thanks.


Let $w \in L$ be a word of length $n$. If $n = 0$ then clearly $w \in L(G)$, so suppose that $n > 0$. For $0 \leq i \leq n$, let $\delta_i$ be the difference between the number of $a$s and $b$s in the first $i$ characters of $w$; thus $\delta_i \geq 0$ for all $i$. We now consider two cases:

Case 1: $\delta_i > 0$ for all $i > 0$. In that case $w = ax$ for some $x \in L$. Induction tells us that $x \in L(G)$, and so $w \in L(G)$.

Case 2: $\delta_i = 0$ for some $i > 0$. In that case $w=axby$, where $|axb| = i$ and $x,y \in L$. Induction tells us that $x,y \in L(G)$, and so $w \in L(G)$.

| cite | improve this answer | |
  • $\begingroup$ Thanks! But I guess in the second case I should pick the minimun $i$ s.t $\delta_i=0$, otherwise I cannot say $x \in L$. Am I wrong? $\endgroup$ – Francesco Gemma Jun 26 '17 at 14:34
  • $\begingroup$ I don't think it makes a difference, but if it does, go ahead and choose the minimum $i$. $\endgroup$ – Yuval Filmus Jun 26 '17 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.