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 manifestation of poetry in external life is formal perfection. True sentiment grows within, and art must represent internal phenomena externally.”
—Franz Grillparzer (1791–1872)
“Children should know there are limits to family finances or they will confuse “we can’t afford that” with “they don’t want me to have it.” The first statement is a realistic and objective assessment of a situation, while the other carries an emotional message.”
—Jean Ross Peterson (20th century)