Formal Statement
If a language L is context-free, then there exists some integer p ≥ 1 such that any string s in L with |s| ≥ p (where p is a "pumping length") can be written as
- s = uvxyz
with substrings u, v, x, y and z, such that
- 1. |vxy| ≤ p,
- 2. |vy| ≥ 1, and
- 3. uv nxy nz is in L for all n ≥ 0.
Read more about this topic: Pumping Lemma For Context-free Languages
Famous quotes containing the words formal and/or statement:
“The bed is now as public as the dinner table and governed by the same rules of formal confrontation.”
—Angela Carter (1940–1992)
“The parent is the strongest statement that the child hears regarding what it means to be alive and real. More than what we say or do, the way we are expresses what we think it means to be alive. So the articulate parent is less a telling than a listening individual.”
—Polly Berrien Berends (20th century)