Esercizi su TM con soluzione

(1)

Corso di

Automi e Linguaggi Formali

Anno Accademico 2014/2015

Esercizi con soluzione

Nome e Cognome: Matricola:

Istruzioni

• Scrivere Nome, Cognome e Matricola su ogni foglio (solo pagine dispari).

• Scrivere la risposta nello spazio bianco al di sotto della domanda; Non `e possibile allegare fogli aggiuntivi, quindi cercate di essere chiari e non prolissi.

• In caso di errori indicate chiaramente quale parte della risposta deve essere considerata; annullate le parti non pertinenti.

• Assicurarsi che non manchi alcun foglio al momento della consegna.

(2)

Problema 1

Definire una TM (tramite la tabella o diagramma di transizione di stato) che dati n uni (1) consecutivi sul nastro, B su tutte le altre posizioni del nastro e testina posizionata sul primo uno (1) a sinistra, termina con 3n + 1 uni (1) consecutivi sul nastro, B su tutte le altre posizioni del nastro e testina posizionata sul primo uno (1). Ad esempio, data la configurazione

⇓

· · · B B B 1 1 B B B · · ·

La TM termina con la seguente configurazione ⇓

· · · B B B 1 1 1 1 1 1 1 B B B · · ·

Soluzione:

Di seguito si mostra la tabella di transizione di stato per una TM che si comporta come richiesto:

0 1 B → q0 (q0, 1, R) (q1, 0, L) q1 (q1, 1, L) (q2, B, R) q2 (q7, 1, L) (q3, B, R) q3 (q3, 0, R) (q3, 1, R) (q4, 1, R) q4 (q5, 1, R) q5 (q6, 1, L) q6 (q6, 0, L) (q6, 1, L) (q2, B, R) ∗q7 (q7, B, R)

Problema 2

Data una stringa w ∈ Σ?_{, la stringa w}R _`_{e ottenuta rovesciando l’ordine dei simboli che costituiscono w.}

Ad esempio, se w = abcd, allora wR_{= dcba.}

Un linguaggio L `e chiuso per rovesciamento se ∀w, w ∈ L ⇒ wR_{∈ L.}

Dimostrare, usando una riduzione, che LR= {codice(Mi)|L(Mi) `e chiuso per rovesciamento} `e

indecidi-bile, dove codice(Mi) `e la stringa che codifica la macchina di turing Mi (come visto a lezione).

Soluzione:

Proviamo che LR, dove

LR= {codice(Mi)|L(Mi) non `e chiuso per rovesciamento}

non è decidibile. Ciò è sufficiente poiché se LRè decidibile, allora lo deve essere anche LR. Consideriamo

il caso non banale in cui |Σ| > 1 (notare che se |Σ| = 1 si ha che w = wR _{e L}

R`e banalmente decidibile).

Costruiamo una riduzione di Lu a LR. Ricordiamo che la riduzione deve essere tale che

codif ica(Mi, w) ∈ Lu⇒ riduzione(codif ica(Mi, w)) ∈ LR

codif ica(Mi, w) 6∈ Lu⇒ riduzione(codif ica(Mi, w)) 6∈ LR

dove codif ica(Mi, w) = codice(Mi)111w, cio`e la stringa ottenuta concatenando la codifica binaria di Mi

vista a lezione con il separatore 111 e infine la string w. Sia ab ∈ Σ?_{. Definiamo riduzione(codif ica(M}

i, w)) = codice(Mi0), dove Mi0 `e la seguente TM:

Sia x la stringa in ingresso a M_i0

M0

i simula Mi su w restituendo

“accetta” se Mi accetta w e x = ab

(3)

Notare che

codif ica(Mi, w) ∈ Lu⇒ Mi(w) = accetta ⇒ L(Mi0) = {ab} ⇒ codice(Mi0) ∈ LR

codif ica(Mi, w) 6∈ Lu⇒ Mi(w) = rifiuta ⇒ L(Mi0) = ∅ ⇒ codice(Mi0) 6∈ LR

Quindi non pu`o esistere una TM che accetta, arrestandosi sempre, il linguaggio LR, altrimenti Lusarebbe

decidibile!

Problema 3

Definire una TM (tramite la tabella o diagramma di transizione di stato) che data una stringa di 0 e 1 sul nastro, B su tutte le altre posizioni del nastro e testina posizionata sul primo simbolo (0 o 1) a sinistra, termina l’esecuzione in uno stato di accettazione solo se il numero di 0 `e uguale al numero di 1. Ad esempio, la configurazione

⇓

· · · B B B 0 1 1 0 1 0 B B B · · · `e accettata, mentre la configurazione

⇓

· · · B B B 1 0 0 1 1 B B B · · · non `e accettata.

Soluzione:

Di seguito si mostra la tabella di transizione di stato per una TM, con alfabeto di nastro {0, 1, X, B}, che si comporta come richiesto:

0 1 X B → q0 (q1, B, R) (q2, B, R) (q0, B, R) (q4, B, R) q1 (q1, 0, R) (q3, X, L) (q1, X, R) q2 (q3, X, L) (q2, 1, R) (q2, X, R) q3 (q3, 0, L) (q3, 1, L) (q3, X, L) (q0, B, R) ∗q4