Automi a stati finiti ed espressioni regolari

Nei post relativi agli automi a stati finiti e alle espressioni regolari, abbiamo visto alcuni esempi di generazione e riconoscimento di semplici stringhe di caratteri costruite su un alfabeto.

Le espressioni regolari sono strumenti che consentono di rappresentare, in modo estremamente sintetico, intere famiglie di stringhe dalla struttura anche piuttosto complessa. Abbiamo visto che, un po’ come avviene nelle espressioni algebriche, è possibile definire degli operatori, come la concatenazione, l’ unione  e la stella di Kleene, per costruire espressioni in grado di generare famiglie di stringhe dalla struttura ben definita.

Abbiamo visto che, ad esempio, l’espressione regolare

a(b+c)b*

ammette come soluzione, cioé genera, questo insieme di stringhe:

{ab, ac, abb, abbb…., acb, acbbb …}

Parlando di grafi e di automi a stati finiti, abbiamo visto che è possibile costruire un’automa in grado di riconoscere stringhe aventi struttura specifica. In questo post esploriamo questo interessante teorema:

per ogni espressione regolare esiste un automa a stati finiti in grado di riconoscere il linguaggio generato

In questa sede non ne diamo una dimostrazione formale, ma forniamo gli strumenti tecnici per costruire l’automa riconoscitore. E’ un processo molto semplice, costituito su poche operazioni fondamentali.

Abbiamo detto che un automa è un insieme di stati, archi e simboli che etichettano gli archi. Gli automi hanno due stati speciali, lo stato iniziale e lo stato finale. A partire da una espressione regolare, si costruisce un automa a stati finiti che ne riconosce il linguaggio applicando pochissime regole.

Lo stato iniziale si distingue per essere l’una con una freccia entrante e nessuno stato precedente, e quello finale per una doppia bordatura.

La stringa vuota è riconosciuta da uno stato che è, contemporaneamente, iniziale e finale. Quindi ε è riconosciuta da:

La concatenazione di due porzioni di espressione regolare si costruisce connettendo gli automi che le riconoscono con un arco, su cui è stato posto l’elemento corrispondente del vocabolario. Quindi, ad esempio, la stringa ab è riconosciuta da:

 

La Stella di Kleene si realizza ponendo un arco che rientra all’ingresso stesso della porzione di espressione da ripetere indefinitamente, ad esempio, questo automa riconosce la stringa (ab)*:

 

Notate che, siccome l’espressione (ab)* è soddisfatta anche dalla stringa vuota ε, l’automa ha uno stato iniziale che è anche finale.

Infine, l’unione si riconosce ponendo due archi uscenti con il corrispondente elemento dell’alfabeto. Ad esempio, a+b è riconosciuta da questo automa:

 

L’automa che riconosce l’espressione regolare a(b+c)b* è quindi:

 

L’insieme di stringhe generato dalle espressioni regolari e riconosciuto dai relativi automi a stati finiti è anche detto linguaggio. Abbiamo presentato entrambi come strumenti con cui si può giocare in diversi modi. Eppure automi ed espressioni regolari sono oggetti matematici dotati di un formalismo ben preciso e di potenzialità espressive caratteristiche. Torneremo in post successivi sulle varie tipologie di linguaggi e sulla classe di oggetti astratti in grado di riconoscerli.

Share
Questa voce è stata pubblicata in Teoria e Pratica e contrassegnata con , , , , , , , , . Contrassegna il permalink.

6 risposte a Automi a stati finiti ed espressioni regolari

  1. pierprogramm scrive:

    Grazie! Spiegazione perfetta! 🙂

  2. roberta scrive:

    Infinite grazie per la spiegazione!! 🙂

  3. Francesco scrive:

    Grazie per l’articolo! Molto utile :), tutta via vorrei porre una domanda:
    Se invece di (a+b) avessi (ab+a*c)?

    • LidiMatematici scrive:

      Come da articolo, la serie ab si costruisce ponendo in serie due nodi che consumino a e b, mentre in parallelo si pone a* (ricciolo sul nodo a consumare la a) in serie con c !

  4. Maurizio Generosi scrive:

    Ottima spiegazione. Complimenti! Se io, però, avessi l’espressione regolare
    (1+01)* (Lambda+0) come dovrei fare? Quale sarebbe l’automa?

    Fra le due parentesi c’è la concatenazione

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *