A characterization of two-way determinis
β
A.V. Aho; J.D. Ullman
π
Article
π
1970
π
Elsevier Science
π
English
β 731 KB
It is shown that a class of languages is defined by a class of two-way deterministic balloon automata if and only if that class is closed under marked union, marked Kleene closure and the inverse mappings performed by deterministic GSMs that move two ways on the input. Hence, the context sensitive l