Generalisert ikke-deterministisk endelig automat

En generalisert ikke-deterministisk endelig automat, forkortet GNFA, er en ikke-deterministisk automat som på overgangene ikke bare trenger å ha symboler fra alfabetet, men kan ha et regulært uttrykk.

Definisjon

GNFA trenger vi under algoritmen for å omforme en endelig automat til et regulært uttrykk. En GNFA er altså en NFA som har overgangene definert av regulære uttrykk. Et eksempel på en slik GNFA:

Vi ser at det for eksempel fra tilstanden q₂ går en overgang til tilstanden q_f, og den er merket med det regulære uttrykket a^∗ b. Flere krav til en GNFA:

• Starttilstanden q₀ må ha en overgang til alle de andre tilstandene. På figuren ser vi at det går overganger fra tilstanden q₀ til alle de andre tilstandene.
• I en GNFA finnes det bare én sluttilstand, og alle de andre tilstandene har en overgang til denne tilstanden. Som vi ser på figuren, har alle tilstandene en pil som peker til q_f.
• Starttilstanden må ikke være den samme som sluttilstanden. En GNFA har altså minst to tilstander.
• Alle de andre tilstandene, bortsett fra start- og sluttilstanden, må ha overganger til alle de andre tilstandene, bortsett fra start- og sluttilstanden. Inkludert løkker (overgang fra tilstanden q_i til tilstanden q_i).

Omforming av en vanlig NFA til en GNFA

Hvis vi har en NFA, er det enkelt å omforme den til en GNFA.

1. Vi lager en ny starttilstand q_s og lager en epsilonovergang til den opprinnelige starttilstanden.
2. Vi lager en ny sluttilstand q_f og lar epsilonoverganger gå fra alle de opprinnelige sluttilstandene til tilstanden q_f. De opprinnelige sluttilstandene gjør vi til vanlige tilstander.
3. Hvis det et sted finnes flere overganger mellom to tilstander (altså hvis vi fra tilstanden q₁ kommer til tilstanden q₂ både med symbolet 0 og med symbolet 1), slår vi disse reglene sammen til ett regulært uttrykk og forbinder alle de opprinnelige symbolene med union-operatoren (altså vi merker pilen med det regulære uttrykket 0|1).
4. Hvis det i automaten mangler en overgang som etter definisjonen skulle vært der, lager vi den og merker den med det regulære uttrykket ∅. Slik endrer vi ikke språket som automaten aksepterer, for en slik overgang blir aldri utført.

Denne automaten kan vi bruke til å omforme en automat til et regulært uttrykk.