Automat finit nedeterminist generalizat (AFNG)

Automatul finit nedeterminist generalizat, pe scurt AFNG, este un automat nedeterminist care pe tranziții nu are neapărat numai simboluri din alfabet, ci poate avea o expresie regulată.

Definiția

Vom avea nevoie de AFNG în algoritmul de conversie a unui automat finit într-o expresie regulată. Un AFNG este deci un AFN ale cărui tranziții sunt definite prin expresii regulate. Un exemplu de AFNG:

Vedem că, de exemplu, din starea q₂ pornește o tranziție în starea q_f, etichetată cu expresia regulată a^∗ b. Alte cerințe pentru AFNG:

• Starea inițială q₀ trebuie să aibă tranziții în toate celelalte stări. În figură vedem că din starea q₀ pornesc tranziții în toate celelalte stări.
• În AFNG există o singură stare finală, iar toate celelalte stări au o tranziție în această stare. După cum se vede în figură, toate stările au o săgeată îndreptată spre q_f.
• Starea inițială nu are voie să coincidă cu starea finală. Un AFNG are deci cel puțin două stări.
• Toate celelalte stări, în afară de cea inițială și cea finală, trebuie să aibă tranziții în toate celelalte stări, în afară de cea inițială și cea finală. Inclusiv bucle (tranziție din starea q_i în starea q_i).

Conversia unui AFN obișnuit în AFNG

Dacă avem un AFN, conversia în AFNG este simplă.

1. Creăm o nouă stare inițială q_s și o ε-tranziție în starea inițială originală.
2. Creăm o nouă stare finală q_f și din toate stările finale originale ducem ε-tranziții în starea q_f. Stările finale originale devin stări obișnuite.
3. Dacă undeva există o tranziție multiplă (adică dacă din starea q₁ ajungem în starea q₂ atât prin simbolul 0, cât și prin simbolul 1), reunim aceste reguli într-o singură expresie regulată, iar simbolurile originale le legăm prin operatorul de reuniune (adică etichetăm săgeata cu expresia regulată 0|1).
4. Dacă în automat lipsește vreo tranziție care, conform definiției, ar trebui să existe, o creăm și o etichetăm cu expresia regulată ∅. Astfel nu schimbăm limbajul pe care îl acceptă automatul, deoarece o astfel de tranziție nu se efectuează niciodată.

Putem folosi acest automat pentru conversia automatului într-o expresie regulată.