Limited automata and unary languages (Q5915989)

Limited automata, introduced in [Inf. Control 11, No. 1--2, 196--238 (1967, Zbl 0168.25801)] by \textit{T. N. Hibbard}, can be described as (nondeterministic) linear bounded automata that can modify the contents of each tape cell at most \(d\) times, for some fixed constant \(d\); such automata are then also called \(d\)-limited. While \(1\)-limited automata can only recognise rational languages, \(d\)-limited automata with \(d \geq 2\) are known to recognise precisely the context-free languages. Moreover, linear boundedness of these automata is known not to be needed -- one could impose the same restriction on nondeterministic Turing machines and obtain an equally powerful model. The authors continue the research of limited automata from the viewpoint of descriptional complexity as represented, e.g., by \textit{G. Pighizzini} and \textit{A. Pisoni} [Int. J. Found. Comput. Sci. 25, No. 7, 897--916 (2014, Zbl 1320.68114); Fundam. Inform. 136, No. 1--2, 157--176 (2015, Zbl 1335.68128); \textit{M. Kutrib} et al., Inf. Comput. 259, No. 2, 259--276 (2018, Zbl 1390.68404)]. In this paper, they consider descriptional complexity of limited automata over a unary alphabet (as unary context-free languages are rational, such automata can only recognise unary rational languages). They prove that already a conversion of a deterministic \(1\)-limited automaton over a unary alphabet to an equivalent nondeterministic finite automaton may require an exponential number of states. Secondly, it is proved that each context-free grammar \(G\) with a unary alphabet of terminals has an equivalent \(1\)-limited automaton of size polynomial in the size of \(G\).