Nedeterministični končni avtomat

Iz MaFiRaWiki

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

Kaj pomeni to opozorilo?

Za končni avtomat pravimo, da je nedeterminističen (NKA), če se kdaj znajde v situaciji, v kateri ima moč izbirati med različnimi stanji glede na prebrano vsebino in trenutno stanje, sicer je determinističen (DKA).

Nedeterministični končni avtomat definiramo kot peterko \langle Q, \Sigma, \delta, q_0, F\rangle, pri čemer je:

  • Q končna množica stanj
  • Σ končna množica simbolov (abeceda)
  • \delta \subseteq Q \times \Sigma \times Q prehodna relacija
  • q_0 \in Q začetno stanje
  • F \subseteq Q množica sprejemnih ali končnih stanj

Primer

Sestavimo nedeterminističen končni avtomat, ki razpoznava niza "a" in "ab".

Za abecedo vzemimo kar množico {a,b}, začetno stanje označimo s s0, končno s s2. Množica stanj naj bo {s0, s1, s2}.

Zapišimo še prehodno funkcijo:

a
b
S0
{S1, S2}
{}
S1
{}
{S2}
S2
{}
{}

NKA lahko predstavimo z usmerjenim grafom:

Osebna orodja