Generaliseret ikke-deterministisk endelig automat

En generaliseret ikke-deterministisk endelig automat, forkortet GNFA, er en ikke-deterministisk automat, som på sine overgange ikke kun behøver have symboler fra alfabetet, men også kan have et regulært udtryk.

Definition

Vi får brug for GNFA under algoritmen til omdannelse af en endelig automat til et regulært udtryk. En GNFA er altså en NFA, hvis overgange er defineret ved regulære udtryk. Et eksempel på en sådan GNFA:

Vi ser, at der fx fra tilstanden q₂ går en overgang til tilstanden q_f, og den er mærket med det regulære udtryk a^∗b. Yderligere krav til en GNFA:

• Starttilstanden q₀ skal have en overgang til alle andre tilstande. På figuren ser vi, at der fra tilstanden q₀ går overgange til alle andre tilstande.
• I en GNFA findes der kun én accepttilstand, og alle andre tilstande har en overgang til denne tilstand. Som det ses på figuren, har alle tilstande en pil, der peger mod q_f.
• Starttilstanden må ikke være identisk med accepttilstanden. En GNFA har derfor mindst to tilstande.
• Alle andre tilstande end start- og accepttilstanden skal have overgange til alle andre tilstande, bortset fra start- og accepttilstanden. Det gælder også løkker (overgang fra tilstanden q_i til tilstanden q_i).

Omdannelse af en almindelig NFA til en GNFA

Hvis vi har en NFA, er omdannelsen til en GNFA enkel.

1. Vi opretter en ny starttilstand q_s og tegner en epsilon-overgang til den oprindelige starttilstand.
2. Vi opretter en ny accepttilstand q_f og fører epsilon-overgange fra alle de oprindelige accepttilstande til tilstanden q_f. De oprindelige accepttilstande gør vi til almindelige tilstande.
3. Hvis der nogen steder findes en flerdobbelt overgang (dvs. hvis vi fra tilstanden q₁ kommer til tilstanden q₂ både via symbolet 0 og via symbolet 1), slår vi disse regler sammen til ét regulært udtryk og forbinder alle de oprindelige symboler med foreningsoperatoren (dvs. vi mærker pilen med det regulære udtryk 0|1).
4. Hvis der i automaten mangler en overgang, som der ifølge definitionen skulle være, opretter vi den og mærker den med det regulære udtryk ∅. Det ændrer ikke det sprog, som automaten accepterer, fordi en sådan overgang aldrig udføres.

Denne automat kan vi bruge til at omdanne en automat til et regulært udtryk.