Automi a stati

Automi

Creato: May 2, 2022 8:36 AM

Tags: Informatica e Computazione

Descrizione degli automi

Gli automi sono un modello di computazione e di calcolo che permette sempre di dire se una stringa data è accettata o meno. Es: linguaggi regolari → possono essere descritti tramite automi a stati finiti.

Ci sono tre tipi di automi, corrispondenti ai tre tipi di grammatiche presentate precedentemente.

Automi a stati finiti (deterministici)

Un automa parte da uno stato iniziale (ovvero l’inizio della stringa), legge la stringa simbolo per simbolo, fa le transizioni definite (per passare da uno stato all’altro, ovvero da un simbolo all’altro) e, quando ha consumato la stringa, si trova in uno stato finale. Questo stato finale può essere di accettazione (stringa accettata) o non accettazione. Es: automa che modella una porta automatica.

Matrice di transizione

La matrice di transizione rappresenta le regole di transizione fra stati. La matrice di transizione specifica come l’automa cambia il suo stato in base all’input. È una funzione: Funzione di transizione.

Definizione formale e deterministica

Gli automi che noi trattiamo sono sempre deterministici: dati degli input e delle regole di transizione, partendo da uno stato iniziale si arriva sempre a uno stato finale di accettazione o meno. Un automa a stati finiti A è una 5-upla (Q, Σ, δ, q₀, F) dove:

• Q è l’insieme non vuoto di stati.
• Σ è un alfabeto finito non vuoto.
• δ è la funzione di transizione.
• q₀ ∈ Q è lo stato iniziale.
• F è l’insieme degli stati di accettazione.

Per rappresentare graficamente un automa si usa il diagramma degli stati.

Es: automa = ({q₁, q₂, q₃}, {0, 1}, δ, q₁, {q₂})

δ rappresentata come matrice di transizione:

Da qui, posso dedurre il diagramma degli stati: q₂ ha il doppio bordo perché è uno stato di accettazione. Il diagramma degli stati sostituisce tutta la definizione dell’automa.

Esempio di transizioni con input

Se l’input è 1101, si eseguono le seguenti transizioni per arrivare allo stato finale:

• Si parte dallo stato iniziale q₁.
• Input 1 → si transita da q₁ a q₂.
• Input 1 → si transita da q₂ a q₂.
• Input 0 → si transita da q₂ a q₃.
• Input 1 → si transita da q₃ a q₂.

Lo stato finale, ovvero di accettazione, è q₂ → coincide con lo stato accettato, quindi la stringa è accettata da A.

Se X è l’insieme delle stringhe accettate dall’automa A, diciamo che X è il linguaggio di A, ovvero L(A) = X.