Sprawl lemma

The pumping lemma ( growth lemma, pump lemma ; English pumping lemma ) is an important statement of the theory of automata , which allows in many cases to check whether a given language is automatic . Since all finite languages are automatic, this check makes sense only for infinite languages. The term “pumping” in the title of the lemma reflects the possibility of repeated repetition of a certain substring in any string of suitable length of any infinite automaton language.

There is also a proliferation lemma for context-free languages , an even more general statement is the proliferation index lemma .

Content

1 Formulation
2 Proof
3 Reverse wording
4 Literature
5 Links

Wording

For an infinite automaton language $L$ ${\ displaystyle L}$ above the alphabet $V$ ${\ displaystyle V}$ there is such a natural number $n$ ${\ displaystyle n}$ for any word $\alpha \in L$ ${\ displaystyle \ alpha \ in L}$ length not less $n$ ${\ displaystyle n}$ there are words $u,v,w\in V^{*}$ ${\ displaystyle u, v, w \ in V ^ {*}}$ such that $\alpha =uvw$ ${\ displaystyle \ alpha = uvw}$ , $|uv|\leqslant n$ ${\ displaystyle | uv | \ leqslant n}$ , $|v|\geqslant 1$ ${\ displaystyle | v | \ geqslant 1}$ and for any non-negative whole $i$ ${\ displaystyle i}$ chain $uv^{i}w$ ${\ displaystyle uv ^ {i} w}$ is a word of language $L$ ${\ displaystyle L}$ .

Record in quantifiers:

(\exists n\in \mathbb {N} )(\forall \alpha \in L:|\alpha |\geqslant n)(\exists u,v,w\in V^{*}):\,[\alpha =uvw\land |uv|\leqslant n\land |v|\geqslant 1\land (\forall i\in \mathbb {N} \cup \{0\},uv^{i}w\in L)]

{\ displaystyle (\ exists n \ in \ mathbb {N}) (\ forall \ alpha \ in L: | \ alpha | \ geqslant n) (\ exists u, v, w \ in V ^ {*}): \ , [\ alpha = uvw \ land | uv | \ leqslant n \ land | v | \ geqslant 1 \ land (\ forall i \ in \ mathbb {N} \ cup \ {0 \}, uv ^ {i} w \ in L)]}

.

Proof

Let the automaton language $L$ ${\ displaystyle L}$ contains an infinite number of chains and suppose that $L$ ${\ displaystyle L}$ recognized by a deterministic finite state machine $A$ ${\ displaystyle A}$ from $n$ ${\ displaystyle n}$ states . To verify the conclusion of the lemma, we choose an arbitrary chain $\alpha$ ${\ displaystyle \ alpha}$ of this language which has a length $n$ ${\ displaystyle n}$ .

If the state machine $A$ ${\ displaystyle A}$ recognizes $L$ ${\ displaystyle L}$ then the chain $\alpha$ ${\ displaystyle \ alpha}$ allowed by this machine, that is, in the machine $A$ ${\ displaystyle A}$ there is a path of length $n$ ${\ displaystyle n}$ from the initial to one of the final states, marked with chain symbols $\alpha$ ${\ displaystyle \ alpha}$ . This path cannot be simple, it must go exactly through $n+1$ ${\ displaystyle n + 1}$ state while machine $A$ ${\ displaystyle A}$ It has $n$ ${\ displaystyle n}$ states. This means that this path passes at least two times through the same state of the automaton $A$ ${\ displaystyle A}$ , that is, on this path there is a cycle with a repeating state. Let this recurring state $q_{k}$ ${\ displaystyle q_ {k}}$ .

Split the chain $\alpha$ ${\ displaystyle \ alpha}$ into three parts so that $\alpha =uvw$ ${\ displaystyle \ alpha = uvw}$ where $v$ ${\ displaystyle v}$ - subchain translating $A$ ${\ displaystyle A}$ out of state $q_{k}$ ${\ displaystyle q_ {k}}$ again in a state $q_{k}$ ${\ displaystyle q_ {k}}$ , and $w$ ${\ displaystyle w}$ - subchain translating $A$ ${\ displaystyle A}$ out of state $q_{k}$ ${\ displaystyle q_ {k}}$ in final condition. Note that how $u$ ${\ displaystyle u}$ so $w$ ${\ displaystyle w}$ may be empty but the sub-chain $v$ ${\ displaystyle v}$ cannot be empty. But then it’s obvious that the automaton $A$ ${\ displaystyle A}$ must also admit a chain $u v v w$ ${\ displaystyle uvvw}$ because the recurring subchain $v$ ${\ displaystyle v}$ goes through the cyclic path again from $q_{k}$ ${\ displaystyle q_ {k}}$ at $q_{k}$ ${\ displaystyle q_ {k}}$ as well as the chain $u v v v w$ ${\ displaystyle uvvvw}$ , and any kind $u v v . . . v w$ ${\ displaystyle uvv ... vw}$ .

This argument constitutes the proof of the pump lemma.

Reverse wording

Another form of this lemma, which is sometimes more convenient to apply to prove the independence of a certain language, is for the language $L$ ${\ displaystyle L}$ above the alphabet $V$ ${\ displaystyle V}$ consists in the following - if it takes place:

(\forall n\in \mathbb {N} )(\exists \alpha \in L\colon |\alpha |\geqslant n)(\forall u,v,w\in V^{*}\colon \alpha =uvw\land |v|\geqslant 1\ \land |uv|\leqslant n)(\exists i\in \mathbb {N} \cup \{0\})uv^{i}w\not \in L

{\ displaystyle (\ forall n \ in \ mathbb {N}) (\ exists \ alpha \ in L \ colon | \ alpha | \ geqslant n) (\ forall u, v, w \ in V ^ {*} \ colon \ alpha = uvw \ land | v | \ geqslant 1 \ \ land | uv | \ leqslant n) (\ exists i \ in \ mathbb {N} \ cup \ {0 \}) uv ^ {i} w \ not \ in L}

that language $L$ ${\ displaystyle L}$ - non-automatic.

To prove that the language is not automatic, one can also use the fact that the intersection of regular languages is regular. So, directly apply the lemma on pumping to the language of regular bracket structures in the alphabet $\{(,)\}$ ${\ displaystyle \ {(,) \}}$ problematic, but its intersection with the language $(^{*})^{*}$ ${\ displaystyle (^ {*}) ^ {*}}$ gives language $(^{n})^{n}$ ${\ displaystyle (^ {n}) ^ {n}}$ whose autonomy follows trivially from the pumping lemma.

Literature

John Hopcroft , Rajeev Motwani , Jeffrey Ullman . Introduction to Automata Theory, Languages, and Computation. - M .: "Williams" , 2002. - S. 528. - ISBN 0-201-44124-1 .

Links

Formal languages and grammar
Pentus, A.E., Pentus, M.R. Theory of formal languages. Study guide . M., 2004
Serebryakov V. A. , Galochkin M. P., Gonchar D. R., Furugyan M. G. Theory and implementation of programming languages - M .: MZ-Press, 2006, 2nd ed. - ISBN 5-94073-094-9
Automata structures (inaccessible link from 13-05-2013 [2347 days] - history )