Language of CFG: $S to aS | aSbS | varepsilon$

Question

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_1dots 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.

Yuval Filmus · Answer

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

Language of CFG: $S to aS | aSbS | varepsilon$

One Answer

Add your own answers!

Ask a Question