Macchina di Turing

[mictrt]

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?

[Rggb1]

@Deckard
Ma infatti è lì che volevo farlo arrivare... ha progettato una MdT(*) che riconosce le stringhe palindrome su '01', dovrebbe arrivare facilmente a progettarne una per quel linguaggio; il mio è un tentativo - come il tuo - di far capire che in pratica tutto ciò di cui ha bisogno lo ha già davanti al naso.

(*) Vado a memoria e non ho verificato, ma mi sembra anche sia corretta; vedi i post precedenti.

[mictrt]

questa l'ho fatta seguendo il mio ragionamento senza scomodare libri o esercizi gia fatti...che ne dite?

[Rggb1]

Il tuo approccio mi sembra complicato, e non l'ho verificato.

Prova così, mi sembra molto più semplice:
- se trovi 'a' la cancelli (con blank) e scorri tutta la stringa a destra (quindi fino a blank);
- cancelli due b alla fine, scorri la stringa a sinistra (fino a blank), e ricominci;
- se rimane la stringa vuota, la macchina accetta.

[mictrt]

grazie Rggb sei un grande non ci ero arrivato....ci ho perso tantissimo tempo invece tu in 2 secondi hai trovato una soluzione...cmq ora posto il mio(tuo)lavoro....

[Rggb1]

Rispondo con ritardo (ero fuori), ma comunque confermo che la tua MdT è corretta, a quel che vedo - comunque basta verificare con JFlap.

Come vedi, non c'è niente di complicato nella creazione delle MdT, basta un po' di esercizio (e del resto questo è utilissimo).