Yleistetty epädeterministinen äärellinen automaatti

Yleistetty epädeterministinen äärellinen automaatti, lyhyesti GNFA, on epädeterministinen automaatti, jonka siirtymissä ei tarvitse olla pelkästään aakkoston symboleja, vaan niissä voi olla säännöllinen lauseke.

Määritelmä

Tarvitsemme GNFA:ta algoritmissa, jolla äärellinen automaatti muunnetaan säännölliseksi lausekkeeksi. GNFA on siis NFA, jonka siirtymät on määritelty säännöllisillä lausekkeilla. Esimerkki tällaisesta GNFA:sta:

Näemme, että esimerkiksi tilasta q₂ johtaa siirtymä tilaan q_f, ja se on merkitty säännöllisellä lausekkeella a^∗ b. GNFA:lle on lisäksi muita vaatimuksia:

• Alkutilasta q₀ täytyy olla siirtymä kaikkiin muihin tiloihin. Kuvassa näemme, että tilasta q₀ johtavat siirtymät kaikkiin muihin tiloihin.
• GNFA:ssa on vain yksi lopputila, ja kaikista muista tiloista on siirtymä tähän tilaan. Kuten kuvasta näkyy, kaikista tiloista on nuoli tilaan q_f.
• Alkutila ei saa olla sama kuin lopputila. GNFA:ssa on siis vähintään kaksi tilaa.
• Kaikista muista tiloista paitsi alku- ja lopputilasta täytyy olla siirtymät kaikkiin muihin tiloihin paitsi alku- ja lopputilaan. Silmukat mukaan lukien (siirtymä tilasta q_i tilaan q_i).

Tavallisen NFA:n muuntaminen GNFA:ksi

Jos meillä on jokin NFA, muuntaminen GNFA:ksi on helppoa.

1. Luomme uuden alkutilan q_s ja luomme epsilon-siirtymän alkuperäiseen alkutilaan.
2. Luomme uuden lopputilan q_f ja johdamme kaikista alkuperäisistä lopputiloista epsilon-siirtymät tilaan q_f. Alkuperäisistä lopputiloista teemme tavallisia tiloja.
3. Jos jossakin on useita siirtymiä (eli jos tilasta q₁ pääsee tilaan q₂ sekä symbolilla 0 että symbolilla 1), yhdistämme nämä säännöt yhdeksi säännölliseksi lausekkeeksi ja liitämme kaikki alkuperäiset symbolit yhdisteoperaattorilla (eli merkitsemme nuolen säännöllisellä lausekkeella 0|1).
4. Jos automaatista puuttuu jokin siirtymä, jonka määritelmän mukaan pitäisi olla siinä, luomme sen ja merkitsemme sen säännöllisellä lausekkeella ∅. Näin emme muuta automaatin hyväksymää kieltä, koska tällaista siirtymää ei koskaan tehdä.

Tätä automaattia voimme käyttää automaatin muuntamiseen säännölliseksi lausekkeeksi.