Generaliserad icke-deterministisk ändlig automat

En generaliserad icke-deterministisk ändlig automat, förkortat GNFA, är en icke-deterministisk automat vars övergångar inte bara behöver ha symboler ur alfabetet utan också kan ha reguljära uttryck.

Definition

Vi behöver en GNFA i algoritmen för att omvandla en ändlig automat till ett reguljärt uttryck. En GNFA är alltså en NFA vars övergångar är definierade av reguljära uttryck. Ett exempel på en sådan GNFA:

Vi ser till exempel att det från tillståndet q₂ går en övergång till tillståndet q_f som är märkt med det reguljära uttrycket a^∗ b. Ytterligare krav på en GNFA:

• Starttillståndet q₀ måste ha en övergång till alla andra tillstånd. I figuren ser vi att det går övergångar från q₀ till alla andra tillstånd.
• En GNFA har bara ett sluttillstånd, och alla andra tillstånd har en övergång till det. Som du ser i figuren har alla tillstånd en pil som pekar mot q_f.
• Starttillståndet får inte vara samma som sluttillståndet. En GNFA har därför minst två tillstånd.
• Alla andra tillstånd, utom start- och sluttillståndet, måste ha övergångar till alla andra tillstånd utom start- och sluttillståndet. Det gäller också loopar (en övergång från tillståndet q_i till tillståndet q_i).

Omvandling av en vanlig NFA till en GNFA

Om vi har någon NFA är omvandlingen till en GNFA enkel.

1. Vi skapar ett nytt starttillstånd q_s och en epsilonövergång till det ursprungliga starttillståndet.
2. Vi skapar ett nytt sluttillstånd q_f och drar epsilonövergångar från alla ursprungliga sluttillstånd till q_f. De ursprungliga sluttillstånden blir vanliga tillstånd.
3. Om det någonstans finns flera övergångar (dvs. om vi kommer från tillståndet q₁ till tillståndet q₂ både med symbolen 0 och med symbolen 1) slår vi ihop reglerna till ett enda reguljärt uttryck och förenar alla ursprungliga symboler med unionsoperatorn (dvs. vi märker pilen med det reguljära uttrycket 0|1).
4. Om automaten saknar någon övergång som enligt definitionen ska finnas, skapar vi den och märker den med det reguljära uttrycket ∅. Då ändrar vi inte språket som automaten accepterar, eftersom en sådan övergång aldrig utförs.

Den här automaten kan vi använda för att omvandla en automat till ett reguljärt uttryck.