Nedeterministični končni avtomati s praznimi prehodi

Iz MaFiRaWiki


Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Nedeterministični končni avtomat posplošimo tako, da dovolimo spremembo stanja, pri kateri avtomat ne prebere naslednjega znaka. Pravimo, da avtomat naredi prehod pri prazni besedi ε.

Tak avtomat je peterka \langle Q, \Sigma, \delta, q_0, F\rangle, pri čemer je:

  • Q končna množica stanj
  • Σ abeceda
  • \delta \subseteq Q \times (\Sigma \cup \{\epsilon\}) \times Q prehodna relacija
  • q0 začetno stanje
  • F \subseteq Q množica sprejemnih ali končnih stanj

Kot vidimo, so komponente iste kot pri NKA, spremenila se je le domena prehodne relacije.

Primer

Definirajmo končni avtomat nad abecedo {0,1} razpoznava nize, ki imajo sodo število ničel ali sodo število enic.

M = (S, Σ, T, s0, A) pri čemer je:

  • Σ = {0, 1},
  • S = {S0, S1, S2, S3, S4},
  • s0 = {S0},
  • A = {S1, S3}

Prehodno funkcijo T pa definiramo takole s pomočjo tabele:

0
1
ε
S0
{}
{}
{S1, S3}
S1
{S2}
{S1}
{}
S2
{S1}
{S2}
{}
S3
{S3}
{S4}
{}
S4
{S4}
{S3}
{}

M ponazorimo z naslednjim usmerjenim grafom:

Image:NFAexample.png

M si lahko predstavljamo kot unijo dveh determinističnih končnih avtomatov: množica stanj enega je {S2, S1}, drugega pa {S3, S4}.

Jezik, ki ga razpoznava M lahko zapišemo z regularnim izrazom (1^*(01^*01^*)^*) \cup  (0^*(10^*10^*)^*).


ε-ZAPRTJE


ε-ZAPRTJE(q), q∈Q, definiramo kot množico vseh stanj p (p∈Q), za katere obstaja pot med p in q označena z ε.

Primer

Naslednji usmerjeni graf ponazarja končni avtomat s praznimi prehodi:

ε-ZAPRTJE(s0) = {s0, s1, s2}.

ε-ZAPRTJE(P), kjer je P množica stanj (P∈P(Q)), definiramo kot unijo \bigcup_{q\in\mathbf{P}}ε-ZAPRTJE(q).

Razširitev prehodne funkcije NKA-ε

Prehodno funkcijo NKA-ε δ : Q × Σ ∪{ε} → P(Q) razširimo do funkcije δ* : Q × Σ* → P(Q), tako, da bodo v δ*(q,w) vsa stanja p, za katera bo obstajala pot med q in p po poteh niza w in morebiti še kakšnega praznega prehoda.

Sedaj definiramo δ*:

  • δ*(q,ε) = ε-ZAPRTJE(q)
  • δ*(q,wa) = ε-ZAPRTJE(P) za w∈Σ*, a∈Σ in P = {p | za nekatere r v δ*(q,w), je p v δ(r,a)}

Spet lahko δ in δ* razširimo na množice stanj na sledeč način:

  • δ(R,a) = \bigcup_{q\in\mathbf{R}}δ(q,a)
  • δ*(R,w) = \bigcup_{q\in\mathbf{R}}δ*(q,a) (R∈P(Q))

δ*(q,a) ni nujno enaka δ(q,a), saj δ*(q,a) vsebuje vsa stanja, ki so dosegljiva q po poteh označenih z a in praznih prehodih, medtem ko δ(q,a) vsebuje le stanja, ki so dosegljiva po poteh označenih z a. Podobno δ*(q,ε) ni nujno enaka δ(q,ε).


Sedaj definiramo jezik, ki ga razpoznava M=\langle Q, \Sigma, \delta, q_0, F\rangle:

  • L(M)={w | δ*(q0,w) vsebuje končno stanje}.

Glej tudi

Osebna orodja