Re: CFGs vs. "declare variable before use"

Hi,


It is not too hard. Just use pumping lemma for KF-languages.


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. To do this, look on vwx string from pumping lemma and try to
understand where in z=0^n1^n0^n1^n it may be. There are 5 cases and no
one from them is true. For example, let vwx is in first zeros, so that
vwx belongs to first 0^n. Then vw=0^k, where k>0. What is uwy? uwy
begins with 0^(n-k)1^n. As |uwy|=4n-k and uvy=tt, then |t|=2n-k/2. So,
t is not in first block of ones and is completed by 0. But, last simbol
of uwy is 1, so uwy cannot be tt.




Edsko de Vries,
> a common statement I read about the limitations of CFGs is that they
> cannot be used to express the requirement that "variables must be
> declared before they are used". However, I have been unable to find
> any formal justifications for this statement (e.g., in the style of
> the proof using the pumping lemma that a^n b^n c^n is not a context
> free language). Could anyone point me to some relevant literature?
> Also, are people aware of any other limitations of CFGs, esp. in the
> context of (the semantics of) programming languages, such as the one I
> mentioned, preferably with proofs?

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