configurazione

Nei DFA

È una “fotografia” dell’automa a stati finiti (DFA) in un determinato istante. È una coppia (stato dell’automa, stringa) in $Q\times {\Sigma }^{\star }$, ad esempio $(q_3,x)\in Q\times {\Sigma }^{\star }$.

N.B.: $q_n$ è la stringa che rimane da leggere, non quella letta fino a quel momento. a ogni transizione, l’automa consuma il carattere sinistro.

Se $w$ è l’input, $(q_0,w)$ è la configurazione iniziale.

$\delta$ mette in relazione le configurazioni $a$ è in relazione con un’altra configurazione $b$ se l’aggiunta di un carattere allo stato di $a$ permette di raggiungere lo stato della configurazione $b$.

Chiamiamo la relazione $A{⊢}_{M}B$, cioè la configurazione $A$ “porta” alla configurazione “B”.

$$(p,ax){⊢}_M(q,x)⟺\delta (p,a)=qa\in \Sigma ,x\in {\Sigma }^{\star },p\in Q,q\in Q$$

Si può estendere per catturare tante iterazioni successive, si fa considerando la chiusura riflessiva e transitiva (come con gli assiomi e la chiusura di Armstrong).

• chiusura riflessiva: $M$ non cambia stato se non legge niente $(q,x){⊢}_M^{\star }(q,x)$
• chiusura transitiva: Se $(q,aby){⊢}_M(p,by)\wedge (p,by){⊢}_M(r,y)⟹(q,aby){⊢}_M^{\star }(r,y)$

Conseguenza: $M\text{accetta}X\in {\Sigma }^{\star }⟺(q_0,x){⊢}_M^{\star }(q,\epsilon )q\in F$. Ciò è esprimibile anche come ${\delta }^{\star }(q_0,x)\in F$.

Nei NFA

In un NFA $N$ le configurazioni sono $(q,x)\in Q\times {\Sigma }_{\epsilon }$.

$$(p,ax){⊢}_N(q,x)$$ $$q\in \delta (p,a)$$

Come per i DFA, si può estendere ${⊢}_N$ per riflessione e transitività:

$$N\text{accetta}w⟺\exists \in F:(q_0,w){⊢}_N^{\star }(q,\epsilon )\text{(esiste almeno un cammino che accetta)}$$