2.5.2 Určení konstanty pumping lemmatu

Konstanta pumping lemma \(p\) je přirozené (nenulové) číslo, které existuje pro každý regulární jazyk.

Připomeňme si znění pumping lemma:

\[ \text{Nechť } L \text{ je regulární jazyk} \implies (\exists p \ge 1)(\forall w \in L) [|w| \ge p \implies (\exists x, y, z \in \Sigma^*) (w = xyz \land |xy| \le p \land |y| \ge 1 \land (\forall k \ge 0) xy^kz \in L)] \]

Nejmenší konstanta p

Nejmenší konstanta pumping lemma \(p\) pro konečný jazyk je o jedna větší než je délka nejdelšího řetězce z jazyka.