Per riconoscere linguaggio di livello 3 e necessario un automa a stati finiti, questo può essere definito come
$$Dove:
- $A$ e un alfabeto
- $S$ e l’insieme degli stati
- $S_0$ e lo stato iniziale ($S_0 \in S$)
- $F$ e l’insieme degli stati finali
- $sfn^*$ e la funzione di stato che computa lo stato futuro del sistema
La funzione $sfn$ definisce a partire dallo stato iniziale $S_0$ l’evoluzione del sistema in funzione delle sequenze in ingresso $x$
Linguaggi e riconoscitori #
Un linguaggio di di tipo 3 e non vuoto se il riconoscitore accetta una stringa x di lunghezza $L_x$ minore del numero di stati $N$
Un linguaggio di di tipo 3 e infinito se il riconoscitore accetta una stringa x di lunghezza $N \lt L_x \lt 2N$ dove $N$ e il numero di stati del automa
Da riconoscitori a generatori #
La differenza fra riconoscitori di un linguaggio a generatori dello stesso e dipende da un cambio di prospettiva nella loro descrizione, riprendendo l’esempio di cui sopra:
l’automa dallo stato $C$ si sposta in $A$ con input $a$
Si può ache esprimere come segue:
l’automa dallo stato $C$ genera la stringa a e si sposta nello stato $A$
In questo modo si possono interpretare il grafo di un automa come produzioni di una grammatica
