Repository files navigation

Si progetti ed implementi in linguaggio C standard, senza usufruire di librerie esterne, un interprete di Macchine di Turing non-deterministiche, nella variante anastro singolo e soloaccettori.

La struttura del file di ingresso è la seguente: prima viene fornita la funzione di transizione, quindi gli stati di accettazione e un limite massimo sul numero di passi da effettuare per una singola computazione (per evitare in maniera banale il problema delle macchine che non terminano), infine una serie di stringhe da far leggere alla macchina.

In uscita ci si attende un file contenente 0 per le stringhe non accettate e 1 per quelle accettate; essendoci anche un limite sul numero di passi, il risultato può anche essere U se non si è arrivati ad accettazione.

Convenzioni: Per semplicità i simboli di nastro sono deichar, mentre gli stati sonoint. Il carattere_ indica il simboloblank. La macchina parte sempre dallo stato 0 e dal primo carattere della stringa in ingresso. I caratteriL,R,S vengono usati, come al solito, per il movimento della testina.

Il file di ingresso viene fornito tramite lostandard input, mentre quello in uscita è sullostandard output.

Il file di ingresso è diviso in 4 parti:

• Una prima parte, che inizia contr, contiene le transizioni, una per linea — ogni carattere può essere separato dagli altri da spazi. Per esempio,0 a c R 1 significa che con la transizione si va dallo stato 0 allo stato 1, leggendoa e scrivendoc. La testina viene spostata a destra (R).
• La parte successiva, che inizia conacc, elenca gli stati di accettazione, uno per linea.
• Per evitare problemi di computazioni infinite, nella sezione successiva, che inizia conmax, viene indicato il numero di mosse massimo che si possono fare per accettare una stringa.
• La parte finale, che inizia conrun, è un elenco di stringhe da fornire alla macchina, una per linea.

Ecco un esempio di file di ingresso:

tr0 a C R 10 b C R 21 a a R 11 b b R 12 a a R 22 b b R 21 a C L 32 b C L 33 a a L 33 b b L 33 C c R 44 a C R 54 b C R 65 a a R 55 b b R 55 c c R 55 C c R 76 a a R 66 b b R 66 c c R 66 C c R 87 a C L 98 b C L 99 a a L 99 b b L 99 C c R 44 c c R 104 C c R 1010 c c R 1010 _ _ S 11acc11max180runaabaabbbabbbababababaaababaaa

Il conseguente file di uscita in questo caso è il seguente:

1001