Macchina di Turing
Ragazzi ho anche dei problemi con le macchine di turing...
1) a^n b^n c^n n>0
ho problemi con quest altro esercizio...sempre se quello qui sopra è corretto
2) wwR | w è una qualunque stringa di 0 e 1 <---- wR è w rovesciata cioe letta al contrario...
qualche suggerimento?
1) a^n b^n c^n n>0
ho problemi con quest altro esercizio...sempre se quello qui sopra è corretto
2) wwR | w è una qualunque stringa di 0 e 1 <---- wR è w rovesciata cioe letta al contrario...
qualche suggerimento?
Risposte
nessuno ne sa qualcosa piu' di me?
Ma scusa la domanda qual è? Devi definire le macchine formalmente e provarle su JFLAP?
si le dovrei progettare...e provarle con jflap...
e la macchina di turing del primo post è corretta?
Secondo me no. Hai verificato con JFLAP?
si...accetta abc aabbcc aaabbbccc .....
"mictrt":
si...accetta abc aabbcc aaabbbccc .....
Prova anche 'aaabbcc'.
ora provo ma immagino non funzioni....
provato e ....
giustamente si blocca....
provato e ....
giustamente si blocca....
Interessante, ciò significa che sono un po' arrugginito... ora provo a reimplemetarla. Comunque se hai verificato sei posto.
Per il secondo, direi di procedere confrontanto la prima cifra con l'ultima, la seconda con la penultima e così via; tieni presente che hai in input solo 0 e 1.
Io sono piu' arruginito di te....se hai la possibilita' rintrollala...ora allego al file per jflap...
per il secondo esercizio...ci avevo pensato anche io,ma come faccio a capire quando si deve interrompere?
per il secondo esercizio...ci avevo pensato anche io,ma come faccio a capire quando si deve interrompere?
"mictrt":
provato e ....
giustamente si blocca....
Ho appena ricontrollato e JFLAP mi dice che 'aaabbcc' è accettata, dunque è come dicevo: la macchina non è corretta. Forse non sono così arrugginito
Magari fossi arruginito come te...cmq a me non funziona con quella stringa....ora ti mando il mio file jflap...
http://www.megaupload.com/?d=NLL24XMZ
http://www.megaupload.com/?d=NLL24XMZ
Rispondo solo adesso ché ho avuto un po' da fare... La tua MdT ha una transazione da stato q4 in sé stesso non corretta, infatti usa 'x' (minuscolo); anche correggendo questa imprecisione, rimane non corretta per il riconoscimento del linguaggio dato, infatti accetta anche stringhe tipo 'aaabbcc'. Comunque è facile da rimediare, basta controllare questa condizione: se alla fine sono rimaste alcune 'a' la stringa non viene accettata.
Per il secondo problema: considerando di controllare solo '0' o '1', partendo da inizio stringa:
- se trovi '0', vai alla fine e controlli se c'è '0', se è così lo cancelli, riavvolgi, cancelli il primo '0' e ricominci;
- se trovi '1', idem; rispetto alla situazione di sopra ci saranno stati differenti, ovviamente;
- la MdT finisce in stato finale se la stringa viene cancellata completamente.
Per il secondo problema: considerando di controllare solo '0' o '1', partendo da inizio stringa:
- se trovi '0', vai alla fine e controlli se c'è '0', se è così lo cancelli, riavvolgi, cancelli il primo '0' e ricominci;
- se trovi '1', idem; rispetto alla situazione di sopra ci saranno stati differenti, ovviamente;
- la MdT finisce in stato finale se la stringa viene cancellata completamente.
guarda un po ora
nuovo quesito
mdt per a^n b^2n .... consigli?
mdt per a^n b^2n .... consigli?
un aiutino?
Cioé fammi capire... non hai proprio nessuna idea di come costruire una MdT che riconosca il linguaggio $L=a^n b^(2n)$, nemmeno "a parole"?
Prova a fare un passo indietro e vedi il problema da un altro punto di vista: sapresti scrivere un algoritmo, magari nel linguaggio di programmazione da te preferito, che data in input una stringa $s$ verifica se è della forma sopra descritta, e stampa in uscita il messaggio "Stringa accettata" oppure "Stringa rifiutata" a seconda dei casi?
Se riesci a fare questo, allora sei in grado di fare lo stesso algoritmo per una MdT, e se ci pensi bene è anche facile.
Prova a fare un passo indietro e vedi il problema da un altro punto di vista: sapresti scrivere un algoritmo, magari nel linguaggio di programmazione da te preferito, che data in input una stringa $s$ verifica se è della forma sopra descritta, e stampa in uscita il messaggio "Stringa accettata" oppure "Stringa rifiutata" a seconda dei casi?
Se riesci a fare questo, allora sei in grado di fare lo stesso algoritmo per una MdT, e se ci pensi bene è anche facile.
ok ora ci provo....ma non so come fare a far "contare" la macchina di Turing...piu' tardi posto qualcosa...
le mdt di sopra sono corrette?
le mdt di sopra sono corrette?
"mictrt":
ok ora ci provo....ma non so come fare a far "contare" la macchina di Turing...piu' tardi posto qualcosa..
Finite Automata can add but not multiply.
Turing Machines can compute any computable function.
Turing machines are incredibly more powerful than Finite Automata.
Yet the only difference between a FA and a TM is that
the TM, unlike the FA, has paper and pencil.
Think about it.
It tells you something about the power of writing.
Comunque immagino che il web sia pieno di descrizioni di TM che riconoscono $a^nb^n$, riconoscere $a^nb^{2n}$ non è molto diverso.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo