Automi a stati

Formattazione del testo

Alinguaggio di A, ovvero L(A) = X.Se l'automa non accetta alcuna stringa, allora riconosce il linguaggio 0 (vuoto).L'esempio di prima accetta tutte le stringhe che:

1. terminano con 1
2. terminano con un numero pari di 0 dopo l'ultimo 1

ConfigurazioneSia A un automa a stati finiti, una configurazione di A è un elemento (uqv) con:

• ∈u Σ ultimo simbolo letto della stringa
• ∈q Q stato corrente
• ∈ *Σv insieme di simboli ancora da leggere

Data questa definizione, uno stato può essere:

• iniziale se q = e u = ε q0
• intermedia se u ≠ ε e v ≠ ε ∈
• finale (di accettazione) se q F e v = ε

Cambio di configurazioneIndichiamo con |- la relazione fra due configurazioni = ( ) e = (c u q v cA A A A A B)u q vB B BAutomi 3Diciamo che |- (ovvero possiamo transitare direttamente da a ) se ec c c cA A B A Bsolo se , )δ( = → dallo stato , con input , transito allo statoq u q q u qA B B A B B= → la stringa

che possono essere descritti utilizzando espressioni regolari. Gli automi a stati finiti deterministici sono uno dei modelli computazionali più semplici e sono utilizzati per riconoscere e generare linguaggi regolari. Un automa a stati finiti deterministico è composto da un insieme finito di stati, un alfabeto di simboli di input, una funzione di transizione che specifica come l'automa si muove da uno stato all'altro in base al simbolo di input corrente, uno stato iniziale e un insieme di stati finali. L'automa legge una stringa di simboli di input uno alla volta e si sposta da uno stato all'altro in base alla funzione di transizione. Se alla fine della lettura della stringa l'automa si trova in uno stato finale, allora la stringa è accettata, altrimenti è rifiutata. I linguaggi accettati dagli automi a stati finiti deterministici sono chiamati linguaggi regolari perché possono essere descritti utilizzando espressioni regolari. Un'espressione regolare è una sequenza di simboli che rappresenta un insieme di stringhe. Le espressioni regolari possono essere utilizzate per riconoscere e generare stringhe che appartengono a un determinato linguaggio regolare. Gli automi a stati finiti deterministici sono utilizzati in diversi campi, come la teoria dei linguaggi formali, la compilazione, l'elaborazione del linguaggio naturale e la verifica formale. Sono uno strumento fondamentale nello studio dei linguaggi formali e nella progettazione di algoritmi per il riconoscimento di pattern e la manipolazione di stringhe.definiti anche dalle grammatiche lineari. Quindi, esiste un modo per passare dall'automa che accetta il linguaggio regolare alla grammatica lineare che lo genera. Automi 41 e 0 sono messi in base a quali colonne relative a ogni stato contengono q2. Ricorda: automa A = (Q, Σ, δ, q0, F) Possiamo, così, capire se una stringa è accettata e se è anche L(G L(A1 1A attraverso il parsing: Il primo step è da 2. Automi a stati finiti nondeterministici Nella parte dedicata alle grammatiche e linguaggi abbiamo dimostrato come, tramite un insieme di simboli terminali e un'espressione regolare, possiamo definire il linguaggio degli identificatori di linguaggi di programmazione. Con gli automi deterministici: Automi 5= , , , Questo automa è <{ }, , δ, , { }> ed è deterministico perché A q q q V q q q2 0 1 2 0 1 2 T da uno stato, in base ad archi diversi, vado in un altro stato. Gli automi deterministici sono casi particolari di automi.

nondeterministici → dato un input, possono esserci più stati rispondenti o nessuno. Dunque, nel diagramma a stati, da un’etichetta (stato) possono uscire più archi (input) con lo stesso nome o nessuno. Dal punto di vista della computazione, è come se l’automa seguisse parallelamente più strade (è, diciamo, un modo compatto per rappresentare insieme più automi deterministici). Altra differenza: l’arco uscente da uno stato può essere etichettato da ε, ovvero un input vuoto → la transizione viene fatta senza consumare nessun input.

Definizione formale: ′ ′∣Q ⊆ P D dove è l’insieme potenza di Q tale che = { }Q Q Q Q.

Automi:

Esempio:

Il diagramma degli stati è:

La computazione di un automa non deterministico può essere rappresentata come un diagramma ad albero.

Configurazioni e computazioni:

Il discorso è simile a quello fatto per gli automi deterministici. Una

configurazione di è un elemento (uqv) come definito in precedenza.

N= (u ) = (uSe e ), diciamo che possiamo passare direttamentec q v c q v1 1 1 1 2 2 2 2−da a (ovvero | ) se:c c c c1 2 1 2N∈ ,δ( )q q v2 1 2Automi 7