Estensioni 2006 al Simulatore
Il Simulatore usato negli anni
precedenti includeva già una forma di abbreviazione
sintattica, consistente nel specificare una sequenza di caratteri
anziché un carattere singolo nei campi della quintupla che
indicano il carattere letto da nastro e quello scritto su nastro.
Tale abbreviazione veniva poi espansa in un numero di regole
pari alla lunghezza della sequenza di caratteri, come nell'esempio
seguente:
|
regola con abbreviazione:
|
( stato1, ABCD,
stato2, EFGH, > )
|
|
regole generate
dall'espansione:
|
( stato1, A,
stato2, E, > )
( stato1, B,
stato2, F, > )
( stato1, C,
stato2, G, > )
( stato1, D,
stato2, H, > )
|
La versione 2006 del Simulatore
generalizza questo meccanismo, introducendo i concetti di classe
di simboli e di espansione parallela.
Classi
di simboli
Una classe di simboli è
una abbreviazione sintattica che denota una sequenza di
simboli compresi nell'alfabeto della macchina (con lo spazio primo elemento dell'alfabeto):
!\"#$%&\'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^-{|}
La denotazione è
costituita da una coppia di parentesi quadre []
o graffe {}, contenenti uno o
più simboli appartenenti alla sequenza, o il simbolo di
intervallo (due volte punto) s1..s2,
che indica tutti i simboli compresi fra s1 e s2 nell'alfabeto della
macchina. Inoltre, se il primo carattere all'interno delle parentesi
è un accento circonflesso ^
(in Inglese caret), si intende che la sequenza denotata è
data dall'insieme complementare di quello indicato, ovvero
comprende tutti i simboli non elencati all'interno delle parentesi.
In questo caso, l'ordine della sequenza è quello naturale
dell'alfabeto usato. Infine, il simbolo di barra inversa \
(in Inglese backslash) indica che il successivo carattere deve
essere inteso letteralmente: per esempio, \]
denota il simbolo “]”, non l'eventuale parentesi di
chiusura di una sequenza; \-
denota il simbolo “-” e non lo spazio, ecc. Allo stesso
modo, \\ denota il simbolo
“\”, che altrimenti non sarebbe esprimibile.
NOTA:
se si specificano pida quelle con parentesi. Questo fatto è importante per quanto riguarda l'espansione
parallela discussa in seguito. La classe di caratteri senza parentesi è stata mantenuta per
compatibilità con l'estensione precedente della macchina, ed è limitata solo alle
componenti della regola differenti da uno stato.
Gli
esempi seguenti chiariscono la notazione usata per le classi di
simboli:
|
Abbreviazione
|
Sequenza di simboli corrispondente
|
|
[abc]
|
{a, b, c}
|
|
[0..9]
|
{ 0, 1, 2, 3, 4,
5, 6, 7, 8, 9 }
|
|
[^aeiou]
|
qualunque simbolo tranne le vocali, nell'ordine
naturale
|
|
[\[\]()]
|
{ [, ], (, ) }
|
|
[^+\-*/0..9]
|
qualunque simbolo tranne le cifre e i simboli
delle quattro operazioni: +, -, *, /, nell'ordine naturale
|
|
[0..9a..f+\-]
|
{ 0, 1, 2, 3, 4,
5, 6, 7, 8, 9, a, b, c, d, e, f, +, - } (cifre esadecimali
con segno)
|
Le
classi di simboli possono essere usate nei seguenti contesti:
per
indicare uno stato iniziale o finale, nel qual caso può
essere usato un prefisso e/o un postfisso che, unito a ciascuno dei
simboli indicati dalla classe, genera il nome effettivo dello stato.
Per esempio, lo stato indicato in maniera abbreviata con
letto[0..9]r viene espanso
nella sequenza di stati { letto0r,
letto1r, letto2r, letto3r, letto4r, letto5r, letto6r, letto7r,
letto8r, letto9r }.
per
indicare un simbolo letto o da scrivere, nel qual caso la classe
fornisce direttamente la sequenza dei simboli indicati. Per esempio,
[0..9] viene espanso nella
lista di simboli { 0, 1, 2, 3, 4, 5,
6, 7, 8, 9 } (analogamente a quanto possibile con la
precedente notazione 0123456789,
che comunque rimane disponibile).
per
indicare una direzione di movimento, nel qual caso la classe deve
denotare una sequenza composta esclusivamente di simboli >
e <. Per esempio, [>>><]
viene espanso nella lista di direzioni { >,
>, >, < }.
Espansione
parallela
Abbiamo
visto sopra che le classi di simboli possono essere delimitate da
parentesi quadre [] o da parentesi graffe {}. In aggiunta, è
possibile usare classi senza delimitatori, come per le vecchie
sequenze del tipo 0123456789
(ora esprimibili anche con la sintassi abbreviata 0..9).
Al momento dell'espansione di una regola abbreviata in un insieme di
regole base, i tre diversi gruppi di classi di simboli vengono
espansi parallelamente: tutte le classi delimitate con lo
stesso tipo di parentesi vengono espanse, per ogni regola, nei
simboli che occupano la stessa posizione nella sequenza; classi
delimitate da parentesi diverse vengono invece espanse
indipendentemente (e in combinazione fra loro).
Ciò
consente di esprimere sinteticamente un grande numero di regole
basate su prodotti cartesiani delle corrispondenti sequenze,
come illustrato nei seguenti esempi:
|
Regola abbreviata
|
Espansione delle classi
|
Regole generate dall'espansione
|
|
( s, [0..3], q,
[a..d], > )
In questo caso, le
due classi racchiuse fra parentesi quadre vengono espanse in
parallelo; quando il simbolo letto è 0 (primo elemento di
[0..3]), il simbolo scritto sarà a (primo elemento di
[a..d]), e così via.
|
[0..3] = 0, 1, 2,
3
[a..d] = a, b, c,
d
|
(s, 0, q, a, >)
(s, 1, q, b, >)
(s, 2, q, c, >)
(s, 3, q, d, >)
|
|
( s, [0..9],
riporto[000000001], [1..90], > )
Questa regola mostra
come sia possibile legare il simbolo letto, quello scritto, e il
nome dello stato finale tramite un'unica espansione. In questo
caso, se viene letto un simbolo fra 0 e 8 viene scritto lo stesso
simbolo aumentato di 1 (quindi, fra 1 e 9) e si va nello stato
riporto0; se invece viene letto un 9, si scrive uno 0 e si passa
allo stato riporto1.
|
[0..9] = 0, 1, 2,
3, 4, 5, 6, 7, 8, 9
riporto[000000001]
= riporto0, riporto0, riporto0, riporto0, riporto0, riporto0,
riporto0, riporto0, riporto1
[1..90] = 1, 2,
3, 4, 5, 6, 7, 8, 9, 0
|
(s, 0, riporto0,
1, >)
(s, 1, riporto0,
2, >)
(s, 2, riporto0,
3, >)
(s, 3, riporto0,
4, >)
(s, 4, riporto0,
5, >)
(s, 5, riporto0,
6, >)
(s, 6, riporto0,
7, >)
(s, 7, riporto0,
8, >)
(s, 8, riporto0,
9, >)
(s, 9, riporto1,
0, >)
|
|
( s[0..4], a..d,
r[0..4], [a..d], <><>)
In questa regola si
fa uso di due gruppi di classi, uno senza parentesi e uno fra
parentesi quadre. Ciascun gruppo si espande in sequenze di
lunghezza 4, quindi verranno prodotte complessivamente 16 regole.
Anche in questo caso, le classi corrispondenti vengono espanse in
parallelo (il primo simbolo di ogni sequenza con il primo simbolo
di tutte le altre sequenze che usano lo stesso delimitatore),
mentre classi con delimitatori diversi vengono espanse
indipendentemente.
Nel nostro caso,
tutte le volte che s[0..4] espande in s0, r[0..4] espanderà
in r0 e [a..d] in a (primo simbolo di ciascuna sequenza); quando
s[0..4] espande in s1, r[0..4] espanderà in r1 e [a..d] in
b, ecc.
In ciascuno di
questi casi, a..d e <><> espanderanno,
rispettivamente, nel primo, secondo, terzo e quarto elemento
della sequenza, rispettivamente. Il risultato finale sono le 16
regole visibili accanto.
|
Classi senza
parentesi:
a..d = a, b, c, d
<><>
= <, >, <, >
Classi con parentesi
quadre:
s[0..4] = s0, s1,
s2, s3, s4
r[0..4] = r0, r1,
r2, r3, r4
[a..d] = a, b, c,
d
|
( s0, a, r0, a,
<)
( s0, b, r0, a,
>)
( s0, c, r0, a,
<)
( s0, d, r0, a,
>)
( s1, a, r1, b,
<)
( s1, b, r1, b,
>)
( s1, c, r1, b,
<)
( s1, d, r1, b,
>)
( s2, a, r2, c,
<)
( s2, b, r2, c,
>)
( s2, c, r2, c,
<)
( s2, d, r2, c,
>)
( s3, a, r3, d,
<)
( s3, b, r3, d,
>)
( s3, c, r3, d,
<)
( s3, d, r3, d,
>)
|
|
(rd_[ab], {012},
wr_[ab], {abc}, <)
Anche in questo caso
vengono usati due gruppi di classi, quelle delimitate da [] e
quelle delimitate da {}. Come visto in precedenza, i due gruppi
vengono espansi in parallelo; verranno quindi generate in totale
6 regole.
|
Classi con parentesi quadre:
rd_[ab] = rd_a,
rd_b
wr_[ab] = wr_a,
wr_b
Classi con parentesi graffe:
{012} = 0, 1, 2
{abc} = a, b, c
|
(rd_a, 0, wr_a,
a, <)
(rd_a, 1, wr_a,
b, <)
(rd_a, 2, wr_a,
c, <)
(rd_b, 0, wr_b,
a, <)
(rd_b, 1, wr_b,
b, <)
(rd_b, 2, wr_b,
c, <)
|
Alcuni
esempi
Mostriamo
ora alcuni esempi di utilizzo dei nuovi costrutti. Per ciascun
esempio, sono indicate il testo del problema che viene risolto, una
versione della soluzione usando la sintassi tradizionale, una
versione con la nuova sintassi, e l'espansione delle regole con la
nuova sintassi.
Odometro:
scrivere un programma per macchina di Turing che, ricevuto sul
nastro una stringa di cifre decimali, lasci sul nastro al termine
dell'esecuzione la stringa di cifre corrispondente al numero
iniziale, incrementato di uno. Se il risultato supera il numero di
cifre inizialmente presenti, il programma deve lasciare sul nastro
una stringa di soli 0 (comportamento simile a quello dei normali
contachilometri).
|
Strategia di soluzione
|
Versione abbreviata
|
Versione espansa
|
|
Dapprima (stato 0) ci si posiziona sull'ultima
cifra a destra del numero; quindi (stato 1) si incrementa la
cifra corrente. Se la cifra era compresa fra 0 e 8, viene fatto
l'incremento e l'esecuzione termina. Se invece la cifra corrente
era 9, viene scritto al suo posto uno 0 e si passa a
incrementare la cifra precedente (riporto).
|
(0,[0..9],0,[0..9],>)
(0,-,1,-,<)
(1,[0..8],FINE,[1..9],>)
(1,9,1,0,<)
|
(0,0,0,0,>)
(0,1,0,1,>)
(0,2,0,2,>)
(0,3,0,3,>)
(0,4,0,4,>)
(0,5,0,5,>)
(0,6,0,6,>)
(0,7,0,7,>)
(0,8,0,8,>)
(0,9,0,9,>)
(0,-,1,-,<)
(1,0,FINE,1,>)
(1,1,FINE,2,>)
(1,2,FINE,3,>)
(1,3,FINE,4,>)
(1,4,FINE,5,>)
(1,5,FINE,6,>)
(1,6,FINE,7,>)
(1,7,FINE,8,>)
(1,8,FINE,9,>)
(1,9,1,0,<)
|
Palindrome:
scrivere un programma per macchina di Turing che, ricevuta sul
nastro una stringa sull'alfabeto a-z, lasci il nastro vuoto alla
fine della computazione se e solo se la stringa originale era
palindroma (si dicono palindrome le stringhe che si leggono
identicamente da sinistra a destra o da destra verso sinistra, per
esempio “ailatiditalia” o “satorrotas”).
|
Strategia di soluzione
|
Versione abbreviata
|
Versione espansa
|
|
Posizionati sul primo carattere a sinistra della
stringa, lo cancelliamo, memorizziamo nel nome dello stato il
carattere letto, passando nello stato lettoa
(se abbiamo letto una a)
fino a lettoz (se abbiamo
letto una z). Quindi
scorriamo tutta la stringa, mantenendo memoria nello stato di
quale carattere avevamo letto, e riscrivendo sempre il carattere
letto. Arrivati in fondo alla stringa, ci spostiamo di una cella
a destra (sempre mantenendo il carattere letto originalmente
nello stato), e verifichiamo di trovare all'estremità
sinistra della stringa lo stesso carattere che avevamo letto a
destra. In caso positivo, si cancella il carattere e si ritorna
in cima alla stringa, ripetendo poi l'algoritmo (fino a
consumare tutta la stringa); in caso negativo si interrompe il
calcolo, lasciando sul nastro la parte di stringa non
palindroma.
|
(0,[a..z],letto[a..z],-,>)
(letto[a..z],{a..z},letto[a..z],{a..z},>)
(letto[a..z],-,destra[a..z],-,<)
(destra[a..z],[a..z],ritorno,-,<)
(ritorno,[a..z],ritorno,[a..z],<)
(ritorno,-,0,-,>)
|
(0,a,lettoa,-,>)
...
(0,z,lettoz,-,>)
(lettoa,a,lettoa,a,>)
(lettoa,b,lettoa,b,>)
...
(lettoa,z,lettoa,z,>)
(lettob,a,lettob,a,>)
...
(lettob,z,lettob,z,>)
...
(lettoz,a,lettoz,a,>)
...
(lettoz,z,lettoz,z,>)
(lettoa,-,destraa,-,<)
...
(lettoz,-,destraz,-,<)
(destraa,a,ritorno,-,<)
...
(destraz,z,ritorno,-,<)
(ritorno,a,ritorno,a,<)
...
(ritorno,z,ritorno,z,<)
(ritorno,-,0,-,>)
|
|
|
|