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)
“The honor my country shall never be stained by an apology from me for the statement of truth and the performance of duty; nor can I give any explanation of my official acts except such as is due to integrity and justice and consistent with the principles on which our institutions have been framed.”
—Andrew Jackson (1767–1845)