Progettazione del compilatore - Automi finiti
Gli automi finiti sono una macchina a stati che prende una stringa di simboli come input e cambia il suo stato di conseguenza. Gli automi finiti sono un riconoscimento per le espressioni regolari. Quando una stringa di espressione regolare viene inserita in automi finiti, cambia il suo stato per ogni letterale. Se la stringa di input viene elaborata con successo e gli automi raggiungono il suo stato finale, viene accettata, ovvero la stringa appena alimentata è stata considerata un segno valido della lingua in mano.
Il modello matematico degli automi finiti è costituito da:
- Insieme finito di stati (Q)
- Insieme finito di simboli di input (Σ)
- Uno stato iniziale (q0)
- Insieme di stati finali (qf)
- Funzione di transizione (δ)
La funzione di transizione (δ) mappa l'insieme finito di stato (Q) su un insieme finito di simboli di input (Σ), Q × Σ ➔ Q
Costruzione di automi finiti
Sia L (r) un linguaggio regolare riconosciuto da alcuni automi finiti (FA).
States: Gli stati della FA sono rappresentati da cerchi. I nomi degli stati sono scritti all'interno di cerchi.
Start state: Lo stato da cui iniziano gli automi, è noto come stato iniziale. Lo stato iniziale ha una freccia puntata verso di esso.
Intermediate states: Tutti gli stati intermedi hanno almeno due frecce; uno che indica e un altro che indica da loro.
Final state: Se la stringa di input viene analizzata con successo, gli automi dovrebbero trovarsi in questo stato. Lo stato finale è rappresentato da doppi cerchi. Può avere un numero dispari di frecce che lo puntano e un numero pari di frecce che puntano da esso. Il numero di frecce dispari è maggiore di uno, vale a direodd = even+1.
Transition: La transizione da uno stato a un altro avviene quando viene trovato un simbolo desiderato nell'ingresso. Durante la transizione, gli automi possono passare allo stato successivo o rimanere nello stesso stato. Il movimento da uno stato all'altro viene mostrato come una freccia diretta, dove le frecce indicano lo stato di destinazione. Se gli automi rimangono nello stesso stato, viene disegnata una freccia che punta da uno stato a se stesso.
Example: Assumiamo che FA accetti qualsiasi valore binario a tre cifre che termina con la cifra 1. FA = {Q (q 0 , q f ), Σ (0,1), q 0 , q f , δ}
