Indietro

ⓘ Automa a stati finiti deterministico




Automa a stati finiti deterministico
                                     

ⓘ Automa a stati finiti deterministico

Nella teoria del calcolo, un automa a stati finiti deterministico o deterministic finite automaton è un automa a stati finiti dove per ogni coppia di stato e simbolo in ingresso cè una ed una sola transizione allo stato successivo.

                                     

1. Definizione formale

Un ASFD è una quintupla A = ⟨ Σ, S, δ, s 0, F ⟩ {\displaystyle {\mathcal {A}}=\left\langle \Sigma,S,\delta,s_{0},F\right\rangle } con:

  • s 0 ∈ S {\displaystyle s_{0}\in S} stato iniziale
  • Σ = { a 0, a 1, …, a n } {\displaystyle \Sigma =\{a_{0},a_{1},\ldots,a_{n}\}} insieme finito di simboli chiamato alfabeto
  • F ⊆ S {\displaystyle F\subseteq S} insieme di stati finali
  • δ: S × Σ → S {\displaystyle \delta:S\times \Sigma \to S} funzione di transizione
  • S = { s 0, s 1, …, s m } {\displaystyle S=\{s_{0},s_{1},\ldots,s_{m}\}} insieme finito di stati

Dato un ASFD A = ⟨ Σ, S, δ, s 0, F ⟩ {\displaystyle {\mathcal {A}}=\left\langle \Sigma,S,\delta,s_{0},F\right\rangle }, una configurazione di A {\displaystyle {\mathcal {A}}} è una coppia s, x {\displaystyle s,x}, dove s {\displaystyle s} è uno stato e x {\displaystyle x} una stringa dellalfabeto.

Una configurazione s, x {\displaystyle s,x} è detta:

  • iniziale se s è lo stato iniziale, s = s 0 {\displaystyle s=s_{0}} ;
  • finale se la stringa in input è vuota, x = ε {\displaystyle x=\varepsilon } ;
  • accettante se la stringa in input è vuota e lautoma si trova in uno stato finale, x = ε {\displaystyle x=\varepsilon } e s ∈ F {\displaystyle s\in F}.

La funzione di transizione induce una relazione di transizione ⊢ {\displaystyle \vdash } tra due configurazioni, che associa ad una configurazione dellautoma la configurazione successiva. Dato un ASFD A = ⟨ Σ, S, δ, s 0, F ⟩ {\displaystyle {\mathcal {A}}=\left\langle \Sigma,S,\delta,s_{0},F\right\rangle } e due configurazioni s, x {\displaystyle s,x} e s ′, y {\displaystyle s,y} di A {\displaystyle {\mathcal {A}}}, avremo tra loro una relazione di transizione s, x ⊢ A s ′, y {\displaystyle s,x\vdash _{\mathcal {A}}s,y} se valgono:

  • esiste un simbolo a ∈ Σ {\displaystyle a\in \Sigma } tale che x = a y {\displaystyle x=ay}
  • δ s, a = s ′ {\displaystyle \delta s,a=s}

Una stringa x ∈ Σ ∗ {\displaystyle x\in \Sigma ^{*}} è accettata dallASFD A {\displaystyle {\mathcal {A}}} se, partendo dalla configurazione iniziale con la stringa ed applicando iterativamente le relazioni di transizione, si perviene ad una configurazione accettante. Linsieme delle stringhe accettate dallautoma forma un linguaggio formale chiamato linguaggio riconosciuto dallautoma. Possiamo quindi dire che L A = { x ∈ Σ ∗ | s 0, x ⊢ A ∗ s, ε, s ∈ F } {\displaystyle L{\mathcal {A}}=\{x\in \Sigma ^{*}|s_{0},x\vdash _{\mathcal {A}}^{*}s,\varepsilon,s\in F\}}, ovvero che il linguaggio riconosciuto dallASFD è composto da tutte le stringhe sullalfabeto dato per cui lautoma termina in uno stato finale.

Il teorema di Kleene dimostra che la collezione dei linguaggi riconosciuti da automi a stati finiti deterministici coincide sia con la collezione dei linguaggi regolari che con i linguaggi definiti da espressioni regolari.

Le espressioni regolari sono chiamate anche espressioni razionali e di conseguenza i linguaggi che esse forniscono sono detti linguaggi razionali ; questi termini sono giustificati dal fatto che questi oggetti si possono studiare con metodi algebrici, più precisamente mediante semigruppi finiti.

                                     

2. Funzione delta estesa

Un modo alternativo per descrivere il comportamento dellautoma è quello di definire la funzione di transizione estesa che estende la funzione di transizione dai simboli alle stringhe. Indichiamo la nuova funzione come δ ¯: S × Σ ∗ → S {\displaystyle {\bar {\delta }}:S\times \Sigma ^{*}\to S}.

La sua definizione viene data induttivamente sulla lunghezza della stringa.

  • Base: δ ¯ q, ε = q {\displaystyle {\bar {\delta }}q,\varepsilon=q}.
  • Passo induttivo: δ ¯ q, ω = δ ¯ q, x, a) = δ p, a = r {\displaystyle {\bar {\delta }}q,\omega={\delta }{\bar {\delta }}q,x,a)={\delta }p,a=r}, con ω = x a {\displaystyle \omega =xa} dove a ∈ Σ {\displaystyle a\in \Sigma } e x ∈ Σ ∗ {\displaystyle x\in \Sigma ^{*}}.
  • Ipotesi induttiva: δ ¯ q, x = p {\displaystyle {\bar {\delta }}q,x=p}.

Sfruttando la funzione delta estesa è possibile ridefinire il linguaggio accettato dallautoma come:

L A = { x ∈ Σ ∗ | δ ¯ s 0, x ∈ F } {\displaystyle L{\mathcal {A}}=\{x\in \Sigma ^{*}|{\bar {\delta }}s_{0},x\in F\}}

                                     

3. Esempio

Il seguente esempio è una ASFD A {\displaystyle {\mathcal {A}}}, con un alfabeto binario, che determina se linput contiene un numero pari di zeri.

A = ⟨ Σ, S, δ, s 0, F ⟩ {\displaystyle {\mathcal {A}}=\left\langle \Sigma,S,\delta,s_{0},F\right\rangle } con:

  • S = { S 1, S 2 } {\displaystyle S=\{S_{1},S_{2}\}} stati
  • F = { S 1 } {\displaystyle F=\{S_{1}\}} stati finali
  • s 0 = S 1 {\displaystyle s_{0}=S_{1}} stato iniziale
  • Σ = { 0, 1 } {\displaystyle \Sigma =\{0.1\}} alfabeto binario
  • δ = { δ S 1, 0 = S 2 δ S 1, 1 = S 1 δ S 2, 0 = S 1 δ S 2, 1 = S 2 {\displaystyle \delta =\left\