Question

Let G be the CFG: S → aS | Sb | a | b. Show that no string in L(G) contains ba as substring.

Answer 1

First of all, we can't minimize the given grammar further.

Productions generating terminals are S->a and S->b. Both the productions are not generating 'ba'.

Now, lets assume that no string of length at most k has susbstring 'ba'

Now lets look at the string generated with length k+1.

Step 1 in the derivation must be S->aS or S->Sb.

If the derviation is S->aS then we will be able to generate the strings of kind a*S untill we stop reducing S with the production S->aS. Next if you take S->b or S->a or S->Sb, either of them produces a string containing ba.

If the derviation is S->Sb then we will be able to generate the strings of kind Sb* untill we stop reducing S with the production S->Sb. Next if you take S->b or S->a or S->Sb, either of them produces a string containing ba.

Hence the given CFG wont generate the strings containing 'ba'