Search code examples
grammarautomata

Construct a grammar that generates L = {a^p b^m c^n|n>=0, m>=0, p=m+n}

Construct a grammar that generates L:

L = {a^p b^m c^n|n>=0, m>=0, p=m+n}

Till now I have attempted this much:

S->A
A->aAb|B
B->aBc|epsilon

Is my grammar right?

Solution

  • I can't give the mathematical proof, but let's try to enumerate the strings your grammar can produce:

    ε, ac, aacc, aaaccc, ... (more same # of a and c), ab, aabb, aaabbb, ... (more same # of a and b), aacb, aaaccb, aaacbb, aaaaccbb, ... (more # a which is the same as # b + c)

    Now does:

    a^p b^m c^n

    indicate that the order must be strictly fulfilled? i.e. a first then b then c. if yes, you can see yourself that b and c are actually swapped in your grammar.