A Class of 2-Head Finite Automata for Linear Languages
DOI:
https://doi.org/10.17345/triangle8.89-99Paraules clau:
language, literature, computationResum
Both deterministic and non-deterministic nite state machines (automata) recognize regular languages exactly. Now we extend these machines using two heads to characterize even-linear and linear languages. The heads move in opposite directions in these automata. For even-linear languages, deterministic automata have the same eciency as non-deterministic ones, but for the general case (linear languages) only the non-deterministic version is sucient. We compare our automata to other two-head automata as well.Descàrregues
Les dades de descàrrega encara no estan disponibles.
Descàrregues
Publicades
2018-06-29
Com citar
Nagy, B. (2018). A Class of 2-Head Finite Automata for Linear Languages. Triangle, (8), 89–99. https://doi.org/10.17345/triangle8.89-99
Número
Secció
Articles