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)
“Truth is that concordance of an abstract statement with the ideal limit towards which endless investigation would tend to bring scientific belief, which concordance the abstract statement may possess by virtue of the confession of its inaccuracy and one-sidedness, and this confession is an essential ingredient of truth.”
—Charles Sanders Peirce (1839–1914)