Left-to-right regular languages and two-way restarting automata
Fachbereich Elektrotechnik/Informatik, Universität Kassel,
34109 Kassel, Germany; email@example.com
Accepted: 5 March 2009
It is shown that the class of left-to-right regular languages coincides with the class of languages that are accepted by monotone deterministic RL-automata, in this way establishing a close correspondence between a classical parsing algorithm and a certain restricted type of analysis by reduction.
Mathematics Subject Classification: 68Q45
Key words: Left-to-right regular grammar / two-way restarting automaton / monotonicity.
© EDP Sciences, 2009