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

ANDREI Stefan <stefan@infoiasi.ro>
19 Mar 2002 11:56:07 -0500

          From comp.compilers

Related articles
Grammar for a^n b^m c^n a^m gstragli@tiscalinet.it (Gioele) (2002-03-17)
Re: Grammar for a^n b^m c^n a^m stefan@infoiasi.ro (ANDREI Stefan) (2002-03-19)
Re: Grammar for a^n b^m c^n a^m christl@male.fmi.uni-passau.de (Timon Christl) (2002-03-19)
Re: Grammar for a^n b^m c^n a^m d00-mla@nada.kth.se (Mikael 'Zayenz' Lagerkvist) (2002-03-21)
| List of all articles for this month |

From: ANDREI Stefan <stefan@infoiasi.ro>
Newsgroups: comp.compilers
Date: 19 Mar 2002 11:56:07 -0500
Organization: Compilers Central
References: 02-03-089
Keywords: parse, theory
Posted-Date: 19 Mar 2002 11:56:07 EST

    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


Post a followup to this message

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