Please enable JavaScript.
Coggle requires JavaScript to display documents.
DFA - Coggle Diagram
DFA
Un
automa finito
è una
quintupla
Q
--> Insieme di tutti gli stati
∑ --> Alfabeto = simboli in input
δ
: Q x ∑ --> Q
= Funzione di transizione
Prende in input una coppia (stato attuale e simbolo letto)
Restituisce in output il
nuovo stato
Funzione di transizione estesa
=
δ*
: Q x ∑^(star) --> Q
Stato di partenza
Legge un'intera stringa
Stato di arrivo finale
q0
--> stato iniziale
F
--> Insieme degli stati accettanti
Il diagramma di stato è composto da:
Stati
--> Cerchi del grafo (q1)
Stato iniziale
--> stato di partenza, indicato con freccia
Stato accettante
--> viene evidenziato con doppio
Transizioni
--> le frecce (archi) che collegano gli stati
Come funziona il processo di calcolo?
Legge un input da sinistra a destra
L'elaborazione parte dallo stato iniziale
Viene letto un simbolo alla volta
Seguendo una sola transizione per volta
L'ouput finale
Accettato
Se dopo l'ultimo simbolo è in uno
stato finale
Rifiutato
Linguaggio accettato L(M)
Elabora una stringa e decide se:
Accettarla
Rfiutarla
Deve rispettare 3 condizioni:
Stato iniziale
Transizioni
Stato di arrivo