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

Iz MaFiRaWiki

Naloga: Ali se da s KA razpoznati a^nb^n?

Jeziki, ki jih razpoznavajo končni avtomati so natanko regularni jeziki. Torej lahko pokažemo, da jezik \{a^nb^n, n \in \mathbb{N}\} ni regularen in bomo s tem dokazali, da se ga s končnim avtomatom ne da razpoznati (odgovor na zastavljeno vprašanje je torej ne).


(1) Predpostavimo, da je jezik L regularen.

(2) Torej (iz leme o napihovanju) sledi, da obstaja taka konstanta n \in \mathbb{N},
da za vsako besedo z \in L, za katero velja |z| \ge n, veljajo predpostavke leme:
\exists u,v,w \ni: z = uvw, |uv| \le n, |v| \ge 1.

(3) Izberemo besedo z = a^nb^n: a^nb^n \in L, |a^nb^n| \ge 1.

(4) Edina možna delitev besede anbn na nize u, v in w pri zgornjih zahtevah je u = aj,v = akinw = ankjbn.

\underbrace{aa \ldots a}_j \underbrace{(aa \ldots a)^i}_k \underbrace{aa \ldots a}_{n-k-j} \underbrace{bb \ldots b}_n

A pri i = 2 velja uv^iw = a^{n+k}b^n \in L, saj velja k = |v| \ge 1, zato pa 
n + k = n. 
S tem je neregularnost jezika L dokazana.
Osebna orodja