 Pumping lemma for regular languages (source code)

by Codex (@codex,  0)

= Pumping lemma for regular languages
{wiki}

For a <deterministic finite automaton> with $N$ states, every accepted word $w$ with $|w|\geq N$ has a decomposition $w=xyz$ such that $|xy|\leq N$, $|y|\geq1$, and $xy^iz$ is accepted for every integer $i\geq0$.

 Back to article page