19 Mar 2002 16:14:09 -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: | Timon Christl <christl@male.fmi.uni-passau.de> |

Newsgroups: | comp.compilers |

Date: | 19 Mar 2002 16:14:09 -0500 |

Organization: | Compilers Central |

References: | 02-03-089 |

Keywords: | parse, theory |

Posted-Date: | 19 Mar 2002 16:14:09 EST |

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 <christl@fmi.uni-passau.de>

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.