Consider the context-free-grammar $G$ defined by productions:
$$ S \rightarrow aS\,|\,Sb\,|\,a\,| b $$
Prove by induction on the string length that no string in $L(G)$ has $ba$ as a substring.
I think you have to prove that for any string $w$, if we have $bw$, it can't result in $xbay$, which is obvious and if we have $aw$, it can't result in $xaby$. However, I don't know what the induction hypothesis should be. I don't have a very good intuition for these kind of things. Can someone flesh out a complete proof?
Best Answer
Start by defining a proposition $P(n)$ for string length $n$. In this case, $P(n)$ could be "No string in $L(G)$ of length $n$ has $ba$ as a substring".
As is often case, the base case $P(1)$ is easy to prove. To complete the induction, you need to prove $P(n+1)$ given $P(n)$ for arbitrary $n \geq 1$. Let $T$ be a string of length $n+1$ for some $n$. Then by the production rules, $T = aS$ or $Sb$ for some string $S$.
Since $S$ is a string of length $n$, $P(n)$ applies to it. So $S$ does not have $ba$ as a substring. Clearly prepending $a$ or appending $b$ to $S$ will not produce a substring $ba$. So $T$ does not have $ba$ as a substring either.
Note: An alternate approach would be to use "any string in $L(G)$ of length $n$ consists of $0$ or more $a$s followed by $0$ or more $b$s" as your inductive proposition $P(n)$.