Re: CFGs vs. "declare variable before use"

"Edsko de Vries" <devriese@cs.tcd.ie>
2 Jun 2005 15:02:30 -0400

          From comp.compilers

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)
| List of all articles for this month |

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.