19 Mar 2002 11:56:07 -0500

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) |

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.