Re: Grammar for a^n b^m c^n a^m

    Dear Gioele Stragli,


First, the language L = {a^n b^m c^n a^m | m, n >= 1} is not context free.
This can be proved using Ogden Lemma, which can "pump" the equal number
of symbols at two different places in a word from L.
Therefore, don't try to find a context free grammar able to generate
the language L because you will not get one.


A monotonic grammar able to generate the language L is:


G = ({S,A,B,X}, {a,b,c}, S, P) where the set of productions P are:


1. S -> A a
2. A -> a A c
3. A-> B
4. A -> b
5. B -> b B X
6. B -> b
7. X c -> c X
8. X a -> a a


It can be easily proved that L(G) = L (using induction on the number
of derivation steps). Because the class of monotonic languages equals
to the class of context sensitive languages, this implies that the
language L is context sensitive one.


    Best wishes,
  Stefan Andrei

Return to the comp.compilers page.
Search the comp.compilers archives again.