Comprendo che qualsiasi linguaggio degno di essere usato può codificare una macchina a stati finiti. La mia domanda è l'opposto, è possibile convertire un pezzo di codice arbitrario (diciamo in C) in una macchina a stati finiti funzionalmente equivalente?
per esempio se ho un pezzo di codice con un paio di blocchi di base di llvm (loop, rami ecc.), posso sostituirli tutti con una macchina a stati giganti, che essenzialmente fa lo stesso?
Sì, certo che può.
Vedi Bohm & Documento di Jacopini del 1966 (Sì, cinquant'anni fa), "Diagrammi di flusso, macchine di turing e lingue con solo due regole di formazione" per i dettagli cruenti.
Hanno mostrato che qualsiasi programma, anche un pasticcio di spaghetti GOTO, può essere convertito in un ciclo WHILE attorno a un'istruzione CASE, che insieme implementa una macchina a stati finiti.
Questo è stato un risultato critico sulla strada per la programmazione strutturata. Ha dimostrato, tra le altre cose, che le dichiarazioni GOTO non erano necessarie.
La macchina a stati finiti ha meno potenza di calcolo di una macchina di Turing. Cioè, la Turing Machine può fare cose che le FSM non possono fare. Questo è vero perché l'FSM è limitato in memoria dal numero di stati (finiti).
Il seguente diagramma illustra la relazione tra una macchina a stati finiti e una macchina di turing. Come puoi vedere, la macchina di Turing è costruita sopra gli altri livelli, uno dei quali è la macchina a stati finiti.
Potresti scrivere una macchina statale abbastanza grande da includere qualsiasi pezzo di codice arbitrario? Possibilmente. Ma non avrai una macchina di turing generalizzata, quindi non c'è alcuna garanzia che funzionerà sempre.
No. Considera un pezzo di codice che legge in una stringa di 0 e riconosce se la lunghezza della stringa è un quadrato perfetto (1, 4, 9, 16, 25 ...). C'è una macchina a stati finiti in grado di fare questo? No, poiché l'insieme di tutte queste stringhe non è un set regolare (suggerimento: usa lemma di pompaggio) e una macchina a stati finiti può riconoscere solo un set regolare. Questo esempio è tratto dalla pagina 57 del libro Introduzione alla teoria degli automi, lingue e computazione (1a edizione) di Hopcroft e Ullman (disponibile al link ). Inoltre, i capitoli due e tre di questo libro forniscono una buona introduzione alle macchine a stati finiti, agli insiemi regolari e al lemma del pompaggio. Ci sono molti altri esempi di set non regolari su Internet. Cerca lingue non regolari.
Leggi altre domande sui tag programming-languages language-design finite-state-machine