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 formal Washington dinner party has all the spontaneity of a Japanese imperial funeral.”
—Simon Hoggart (b. 1946)
“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)