We present two restricted versions of one-tape Turing machines. Both characterize the class of context-free languages. In the first version, proposed by Hibbard in 1967 and called limited automata, each tape cell can be rewritten only in the first d visits, for a fixed constant d ≥ 2. Furthermore, for d = 2 deterministic limited automata are equivalent to deterministic pushdown automata, namely they characterize deterministic context-free languages. Further restricting the possible operations, we consider strongly limited automata. These models still characterize context-free languages. However, the deterministic version is less powerful than the deterministic version of limited automata. In fact, there exist deterministic context-free languages that are not accepted by any deterministic strongly limited automaton.
One-tape Turing Machine variants and language recognition / G. Pighizzini. - In: SIGACT NEWS. - ISSN 0163-5700. - 46:3(2015 Sep), pp. 37-55. [10.1145/2818936.2818947]
One-tape Turing Machine variants and language recognition
G. PighizziniPrimo
2015
Abstract
We present two restricted versions of one-tape Turing machines. Both characterize the class of context-free languages. In the first version, proposed by Hibbard in 1967 and called limited automata, each tape cell can be rewritten only in the first d visits, for a fixed constant d ≥ 2. Furthermore, for d = 2 deterministic limited automata are equivalent to deterministic pushdown automata, namely they characterize deterministic context-free languages. Further restricting the possible operations, we consider strongly limited automata. These models still characterize context-free languages. However, the deterministic version is less powerful than the deterministic version of limited automata. In fact, there exist deterministic context-free languages that are not accepted by any deterministic strongly limited automaton.File | Dimensione | Formato | |
---|---|---|---|
arxivLimited.pdf
accesso riservato
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
404.33 kB
Formato
Adobe PDF
|
404.33 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
p37-pighizzini.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
656.98 kB
Formato
Adobe PDF
|
656.98 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.