2 Jun 2005 15:02:30 -0400

Related articles |
---|

CFGs vs. "declare variable before use" devriese@cs.tcd.ie (Edsko de Vries) (2005-05-26) |

Re: CFGs vs. "declare variable before use" wyrmwif@tsoft.org (SM Ryan) (2005-05-28) |

Re: CFGs vs. "declare variable before use" mefrill@yandex.ru (mefrill) (2005-05-28) |

Re: CFGs vs. "declare variable before use" torbenm@diku.dk (2005-05-28) |

Re: CFGs vs. "declare variable before use" cfc@shell01.TheWorld.com (Chris F Clark) (2005-05-28) |

Re: CFGs vs. "declare variable before use" torbenm@diku.dk (2005-05-31) |

Re: CFGs vs. "declare variable before use" gah@ugcs.caltech.edu (glen herrmannsfeldt) (2005-05-31) |

Re: CFGs vs. "declare variable before use" devriese@cs.tcd.ie (Edsko de Vries) (2005-06-02) |

Re: CFGs vs. "declare variable before use" cfc@shell01.TheWorld.com (Chris F Clark) (2005-06-02) |

Re: CFGs vs. "declare variable before use" gah@ugcs.caltech.edu (glen herrmannsfeldt) (2005-06-04) |

Re: CFGs vs. "declare variable before use" mefrill@yandex.ru (mefrill) (2005-06-04) |

Re: CFGs vs. "declare variable before use" mittra@juno.com (Swapnajit Mittra) (2005-06-08) |

Re: CFGs vs. "declare variable before use" sharp@cadence.com (2005-06-08) |

From: | "Edsko de Vries" <devriese@cs.tcd.ie> |

Newsgroups: | comp.compilers |

Date: | 2 Jun 2005 15:02:30 -0400 |

Organization: | http://groups.google.com |

References: | 05-05-21605-05-220 |

Keywords: | parse, theory |

Hey,

First off, thank you for your answer. This is the sort of proof I was

looking for.

*> Pumping Lemma for KF-language:*

*> Let L - KF-language. Then, there is such constant n, that if z - string*

*> belongs L with |z| <= n, then z can be written in z = uvwxy and:*

*> 1. |vwx| <= n.*

*> 2. vx != epsilon (empty string).*

*> 3. uv^iwx^iy belongs L, if i >= 0.*

*>*

*> So, we pump v and x.*

*>*

*> Lets look in simplest language with "declare before use": L={ww: w*

*> belongs to {0,1}*}. L consists of two same 0,1 simbols sequenses. For*

*> example, 0101 (w=01) or 10111011 (w=1011). It is clear the language is*

*> the simplest model of our problem. And let z=0^n1^n0^n1^n. So, z's*

*> example is 0101, 00110011 and etc. It is not hard prove z cannot belong*

*> to L.*

I am presuming that you mean to pick an element z from L; then show

(as you did) that we cannot apply the pumping lemma to the element z

(as you defined it); therefore we can conclude that L is not context

free. (I am a bit confused by your statement "it is not hard to prove

z cannot belong to L", because clearly, z is in L).

Is this type of proof sufficient though? I like it, but I am not sure

it conclusively proofs that a grammar in which variables must be

declared before they are used is not context free. What I am not sure

about is your statement that this is the "simplest model of the

problem". Can that statement be qualified?

Edsko

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.