cerca
Informatica Teorica - Automi a stati finiti
modifica cronologia stampa login logout

Wiki

UniCrema


Materie per semestre

Materie per anno

Materie per laurea


Help

Informatica Teorica - Automi a stati finiti

Torna alla pagina di Informatica Teorica


 :: Informatica Teorica - Automi a stati finiti ::

Appunti del 3 Marzo

Automa a stati finiti

L'automa a stati finiti (o macchina a stati finiti) è il modello computazionale più semplice ma con una quantità limitata di memoria.

Può essere definito formalmente in questo modo:

Un automa a stati finiti è una 5-tupla (Q, Σ, δ, q0, F) dove:

  • Q è l'insieme finito degli stati dell'automa
  • Σ è un insieme finito di simboli chiamato alfabeto
  • δ: Q × Σ → Q è la funzione di transizione che dato uno stato e un simbolo in ingresso indica qual'è lo stato futuro dell'automa
  • q0 ∈ Q è lo stato iniziale dell'automa
  • F ⊆ Q è l'insieme degli stati accettanti

Se A è l'insieme delle stringhe accettate dall'automa M allora A è il linguaggio della macchina M (L(M) = A) e si dice che M riconosce A.

I linguaggi riconosciuti dagli automi a stati finiti si chiamano linguaggi regolari. Un linguaggio è regolare se esiste un automa a stati finiti che lo riconosce.

Ma cosa vuol dire accettare una stringa? Significa che partendo dallo stato iniziale, l'automa deve terminare la sua computazione in uno stato d'accettazione. Più formalmente:

Dato M = (Q, Σ, δ, q0, F) e una stringa d'ingresso w = w1w2w3...wn dove ogni wi ∈ Σ, si dice che M accetta w se esiste una sequenza di stati r0, r1, ..., rn in Q che rispetti le seguenti 3 condizioni:

  • r0 = q0 → la macchina parte dallo stato iniziale
  • δ(ri, wi+1) = ri+1 per i = 0, 1, ..., n-1 → la macchina passa da uno stato all'altro in accordo alla funzione di transizione
  • rn ∈ F → la macchina termina in uno stato accettante

Un esempio di automa a stati finiti è la macchina M che riconosce il linguaggio A = {w | w è una stringa con un numero dispari di 1}:

M = (Q, Σ, δ, q0, F)

dove

  • Q = {q0, q1}
  • Σ = {0, 1}
  • q0 è lo stato iniziale
  • F = {q1}
  • δ =
 01
q0q0q1
q1q1q0

Operazioni sui linguaggi

Siano A e B due linguaggi, definiamo le operazioni di unione, concatenazione e star come segue:

  • unione: AB = {x | xAxB}, ovvero l'insieme delle stringhe che appartengono a ad almeno uno dei due linguaggi
  • concatenazione: AB = {xy | xAyB}, ovvero l'insieme delle stringhe formate da una stringa di A seguita da una di B
  • star: A = {x1x2...xk | k ≥ 0 ∧ xiA}, l'insieme di tutte le concatenazioni delle stringhe di A

Chiusura di un linguaggio

Una collezione di oggetti è chiusa rispetto ad una determinata operazione se applicando l'operazione ai membri della collezione si ottiene un oggetto appartenente ancora alla collezione. Facendo riferimento ai linguaggi possiamo dire che una classe di linguaggi è chiusa rispetto ad un'operazione se applicando l'operazione ai linguaggi della classe otteniamo ancora un linguaggio della stessa classe.

Proprietà dei linguaggi regolari

È possibile dimostrare che i linguaggi regolari sono chiusi rispetto all'operazione di unione, quindi l'unione di due linguaggi regolari è un altro linguaggio regolare:

Siano A1 e A2 due linguaggi regolari e M1 e M2 rispettivamente gli automi a stati finiti che li riconoscono. Vogliamo costruire l'automa M che riconosce il linguaggio A1A2.

M1 = (Q1, Σ, δ1, q1, F1)
M2 = (Q2, Σ, δ2, q2, F2)
M = (Q, Σ, δ, q, F)

Q = Q1 × Q2 = {(r1,r2) | r1 ∈ Q1 ∧ r2 ∈ Q2}
δ : Q × Σ → Q
δ((r1, r2), a) = (δ1(r1, a), δ2(r2, a)), (r1, r2) ∈ Q ∧ a ∈ Σ
q = (q1, q2)
F = {(r1, r2) | r1 ∈ F1 ∧ r2 ∈ F2}

Abbiamo dimostrato per costruzione che esiste l'automa a stati finiti riconoscitore del linguaggio unione, che è quindi un linguaggio regolare.


Torna alla pagina di Informatica Teorica