Re: CFGs vs. "declare variable before use"

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

Return to the comp.compilers page.
Search the comp.compilers archives again.