Esercizi svolti: Intersezione tra automi

Si dovrebbe già sapere che l’automa caratterizza un linguaggio regolare. E sappiamo che la classe dei linguaggi regolari è chiusa rispetto all’intersezione (al contrario della classe dei linguaggi liberi), ciò significa che l’intersezione tra due linguaggi regolari genera un altro linguaggio regolare (quindi caratterizzabile da un automa).
Ora la domanda è: Dati due linguaggi regolari L1 e L2 caratterizzati dagli automi A1(L1) e A2(L2), come faccio a costruirmi l’automa intersezione A(L1 ∩ L2)?

PRIMO MODO: Usare la Legge di De Morgan . Quindi rispettando la priorità degli operatori, complementare A1 e A2 separatamente, fare l’unione dei due automi (la classe dei linguaggi regolari è chiusa anche rispetto all’unione) e infine complementare l’unione.

SECONDO MODO
Formalmente.
Sia A1 il primo automa con Q1 l’insieme dei suoi stati, q0 lo stato iniziale e Σ l’alfabeto del linguaggio regolare caratterizzato.
Sia A2 il secondo automa con Q2 l’insieme dei suoi stati, q’0 lo stato iniziale e Σ l’alfabeto del linguaggio regolare caratterizzato.
Allora l’automa intersezione A con Q=Q1 x Q2 l’insieme degli stati, q00 lo stato iniziale e Σ l’alfabeto è tale che

  • q00 è la coppia di stati (q0, q’0), gli stati iniziali dei due automi;
  • la funzione di transizione (denotata con δ) è definita così ∀ qij ∈ Q, ∀ a ∈ Σ : δ(qij, a) = (δ1(qi, a), δ2(q’j, a)). Quindi ad esempio q0 e q’2 si fondono nello stato q02

Quindi A è ottenuto mettendo in parallelo A1 e A2 e fondendo i loro stati, una transizione comprende le transizioni dello stesso simbolo in entrambi gli stati.

Ecco 2 esempi di applicazione del secondo modo di ottenere l’automa intersezione

  1. Riportiamo gli stati risultanti dal prodotto cartesiano di Q1 x Q2
  2. Da q0 c’è una transizione verso sè stesso con b, da q’0 con b si va in q’1. Quindi da q00 si va in q01, ecc…
  3. Per gli stati finali, osserviamo che q0 e q’0 sono stati finali dei rispettivi automi, quindi q00 è finale

  • Giorgio Papa

    salve, quando l’automa risultante possiede stati pozza e stati irraggiungibili, vanno eliminati in quanto inutili?

    • http://pierprogramm.altervista.org/wordpress pierprogramm

      In generale direi che gli stati irraggiungibili vanno eliminati, mentre gli stati pozzo no. Uno stato è pozzo se, mentre costruisci la stringa, “sfori” cioè non puoi più ottenere una stringa riconosciuta dal linguaggio.
      In ogni caso, dipende dall’esercizio che stai svolgendo.