Lema o napihovanju za regularne jezike

Iz MaFiRaWiki

Naj bo $L$ regularni jezik. Potem za jezik $L$ obstaja neka konstanta $n : = c (L)$ da velja: če je $z \in L$ in $|z| \ge n$ , potem obstajajo $u,v,w \in \Sigma^+$ , da lahko $z$ zapišemo kot $z = u v w$ , da je $|uv|\le n$ in $|v|\ge 1$ in za $\forall i$ velja $uv^i w \in L$ .

[spremeni]

Dokaz

[spremeni]

Uporaba

Lemo o napihovanju uporabljamo predvsem za dokazovanje neregularnosti posameznih formalnih jezikov. Dokaz neregularnosti izbranega jezika $L$ poteka na osnovi dokaza s protislovjem:

Najprej predpostavimo, da je $L$ regularen jezik.
Na osnovi predpostavke, da je jezik L regularen, ugotovimo, da
- za jezik $L$ velja lema o napihovanju in zato
- za jezik $L$ obstaja konstanta $n$ iz leme.
Izberemo neko besedo z, za katero velja
- $z \in L$ in
- $|z| \ge n$ .
Za izbrano besedo z preverimo vse možne delitve na podnize u,v in w
- če za vsako delitev obstaja nek $i$ , da $uv^iw \notin L$ , tedaj jezik ni regularen;
- sicer nismo dokazali ničesar.