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

[Gioele]

As Object .
Does a grammar for this language exist ? Is possible a type 2 Grammar?

Thanks everybody

[ANDREI Stefan]

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

[Timon Christl]

On 17 Mar 2002 22:42:27 -0500, Gioele wrote

> As Object .
> Does a grammar for this language exist ? Is possible a type 2 Grammar?

Lets use the pumping-lemma for context-free languages:

Let L be a context-free language. Then for some k in N, every w in L
with |w| >= k can be written as w = uvxyz where

|v x y| <= k
|v y| >= 1
u v^n x y^n z is in L for all n>=0

is true.

If any of those properties is false the language cannot be a
context-free language.

Lets choose k = n+m and
w = u v x y z
u = a^n
v = b^m
x = <epsilon>
y = c^n
z = a^m.

Then |w|>= k, |v x y| <= k and |v y| >=1, but the last requirement is
not true:

u v^N x y^N z = a^n (b^m)^N (c^n)^N a^m

is not in L for _all_ N>=0. Let N=0, then u v^N x y^N z is a^b a^m,
which is certainly not in L. Thus L cannot be a context-free language.

(No warranty that this proof is correct. Please correct me if I'm wrong).

--
Timon Christl <chr...@fmi.uni-passau.de>

[Mikael 'Zayenz' Lagerkvist]

Sorry to say, but your proof is incorrect.

The pumping lemma for contex-free grammars says that there exists a
string that can be written in the way that you describe. If this
lemma is to be used to disprove that a language is a CF language, one
can not choose the parts uvxyz freely, one must instead show that the
results hold for all possible choices of uvxyz.

In other words, the error is where you say "Lets choose...".

Hope this helps

Mikael Lagerkvist

___________________________________
Mikael 'Zayenz' Lagerkvist
Undergraduate Student
Computer Science
Royal Institute of Technology (KTH)
Stockholm, Sweden