Lema o napihovanju za regularne jezike/Dokaz

Iz MaFiRaWiki

Naj bo M = < Q,Σ,δ,q0,F > končni avtomat, da je L = L(M). Tak avtomat obstaja. Naj bo n: = | Q | in z:=a_1 a_2 \cdots a_m, m \ge n, z \in L. Pri sprejemanju vhodnega niza z avtomat M začne v stanju q0, nato pa opravi m prehodov skozi stanja q_{j_1},q_{j_2},\ldots,q_{j_m}, pri čemer velja \delta(q _{j_{i-1}},a_i)= q_{j_i} za i=1,2,\ldots,m(in pri q0 = qj0).

A zaporedje stanj q_{j_0},q_{j_1},\ldots,q_{j_m} vsebuje m + 1 stanj. A ker je m + 1 > n = | Q | , se neko stanje avtomata M v tem zaporedju ponovi. Obstajata torej indeksa k in l, tako da velja q_{j_k} = q_{j_l}. To pomeni, da zaporedje q_{j_k},q_{j_{k+1}},\ldots,q_{j_l} pri sprejemanju vhodnega niza z ustvari "cikel".


Naj velja

u = a_1a_2 \cdots a_k,
v = a_{k+1}a_{k+2} \cdots a_l in
w = a_{l+1}a_{l+2} \cdots a_m.

Tedaj velja

\hat{\delta}(q_0,u) = q_{j_k},
\hat{\delta}(q_k,v) = q_{j_l} = q_{j_k} in
\hat{\delta}(q_l,w) = \hat{\delta}(q_{j_k},w) = q_{j_m}

pri q_{j_m} \in F. A ker velja \hat{\delta}(q_k,v) = q_{j_k}, velja uv^iw \in L za vsak i \ge 0.


Dokaz bo bolj jasen, če pogledamo primer. Na spodnji sliki je prikazan končni avtomat.

Image:LemaOnapihovanju.png

Končni avtomat razpozna niz abcbcd. Ker je ta beseda daljša kot število stanj končnega avtomata (ta so 4), se nekatera stanja ponovijo. V tem primeru se ponovita stanji q1 in q2. Končni avtomat se pri branju podniza bcbc niza abcbcd pomika od stanja q1 do stanja q2 in nato spet v stanje q1 (ustvari "cikel"). Torej se del vhodnega niza lahko ponovi ali pa je izpuščen. Sledi, da bo končni avtomat sprejel tudi niza abcbcbcd in ad. Niz abcbcd razdelimo na u = a, v = bc in w = bcd. Velja: sprejet bo vsak niz oblike uviw za vsak i \ge 0.(Lahko bi ga razdelili tudi drugače: u = a, v = bcbc in w = d, vendar ne bi bil izpolnjen pogoj leme o napihovanju |uv| \le n)

Osebna orodja