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:
“On every formal visit a child ought to be of the party, by way of provision for discourse.”
—Jane Austen (1775–1817)
“No statement about God is simply, literally true. God is far more than can be measured, described, defined in ordinary language, or pinned down to any particular happening.”
—David Jenkins (b. 1925)