Gegeneraliseerde niet-deterministische eindige automaat

Een gegeneraliseerde niet-deterministische eindige automaat, kortweg GNFA, is een niet-deterministische automaat die op de overgangen niet alleen symbolen uit het alfabet hoeft te hebben, maar ook een reguliere expressie.

Definitie

De GNFA hebben we nodig tijdens het algoritme voor het omzetten van een eindige automaat naar een reguliere expressie. Een GNFA is dus een NFA waarvan de overgangen met reguliere expressies zijn gedefinieerd. Een voorbeeld van zo'n GNFA:

We zien dat bijvoorbeeld vanuit toestand q₂ een overgang naar toestand q_f loopt die is gelabeld met de reguliere expressie a^∗ b. Verdere eisen aan een GNFA:

• De begintoestand q₀ moet een overgang hebben naar alle andere toestanden. In de figuur zien we dat vanuit toestand q₀ overgangen naar alle andere toestanden lopen.
• In een GNFA is er maar één eindtoestand en alle andere toestanden hebben een overgang naar deze toestand. Zoals in de figuur te zien is, hebben alle toestanden een pijl die naar q_f wijst.
• De begintoestand mag niet dezelfde zijn als de eindtoestand. Een GNFA heeft dus minstens twee toestanden.
• Alle andere toestanden, behalve de begin- en de eindtoestand, moeten overgangen hebben naar alle andere toestanden, behalve de begin- en de eindtoestand. Inclusief lussen (een overgang van toestand q_i naar toestand q_i).

Omzetting van een gewone NFA naar een GNFA

Als we een NFA hebben, is het omzetten naar een GNFA eenvoudig.

1. We maken een nieuwe begintoestand q_s en maken een epsilonovergang naar de oorspronkelijke begintoestand.
2. We maken een nieuwe eindtoestand q_f en trekken vanuit alle oorspronkelijke eindtoestanden epsilonovergangen naar toestand q_f. Van de oorspronkelijke eindtoestanden maken we gewone toestanden.
3. Als er ergens een meervoudige overgang bestaat (dus als we vanuit toestand q₁ zowel via symbool 0 als via symbool 1 in toestand q₂ komen), voegen we deze regels samen tot één reguliere expressie en verbinden we alle oorspronkelijke symbolen met de operator vereniging (dus we labelen de pijl met de reguliere expressie 0|1).
4. Als in de automaat een overgang ontbreekt die er volgens de definitie zou moeten zijn, maken we die en labelen we hem met de reguliere expressie ∅. Daarmee veranderen we de taal die de automaat accepteert niet, omdat zo'n overgang nooit wordt genomen.

Deze automaat kunnen we gebruiken om een automaat om te zetten naar een reguliere expressie.