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 = uvw, da je |uv|\le n in |v|\ge 1 in za \forall i velja uv^i w \in L.

Dokaz

Uporaba

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

  1. Najprej predpostavimo, da je L regularen jezik.
  2. 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.
  3. Izberemo neko besedo z, za katero velja
    • z \in L in
    • |z| \ge n.
  4. 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.

Pozorni moramo biti na pravilno izbiro besede z ter na to, da res preverimo vse njene možne delitve.

Primer

Tipičen primer za dokazovanje neregularnosti jezika s pomočjo leme o napihovanju je naslednji:

Ali se da s končnim avtomatom nad abecedo Σ = {a,b} razpoznati jezik \{a^nb^n; n \in \mathbb{N}\}?


Problem razrešimo tako, da pokažemo, da jezik L = \{a^nb^n; n \in \mathbb{N}\} ni regularen.

Rešitev

Rešitev: Ali se da s KA razpoznati a^nb^n?

Glej tudi

Osebna orodja