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.

  • $\begingroup$ Welcome to CS.SE! It looks like you might have accidentally created two accounts. If so, I encourage you to merge them. That will ensure you retain the ability to edit your question, and leave comments under answers if you need clarification on something. We have strict quality standards here -- please reserve the 'answer' box only for material that answers the question. If you want to request clarification on another answer, please leave a comment under it, but don't post it as an 'answer'. Thank you! $\endgroup$ – D.W. Jun 26 '17 at 18:45
  • $\begingroup$ Maybe our reference question can help. $\endgroup$ – Raphael Jun 26 '17 at 20:50

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

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