2015/12/17 by Caron, Pascal, Mignot, Ludovic, Miklarz, Clément
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.1512.05475
A regular language is k-lookahead deterministic (resp. k-block deterministic) if it is specified by a k-lookahead deterministic (resp. k-block deterministic) regular expression. These two subclasses of regular languages have been respectively introduced by Han and Wood (k-lookahead determinism) and by Giammarresi et al. (k-block determinism) as a possible extension of one-unambiguous languages defined and characterized by Brüggemann-Klein and Wood. In this paper, we study the hierarchy and the inclusion links of these families. We first show that each k-block deterministic language is the alphabetic image of some one-unambiguous language. Moreover, we show that the conversion from a minimal DFA of a k-block deterministic regular language to a k-block deterministic automaton not only requires state elimination, and that the proof given by Han and Wood of a proper hierarchy in k-block deterministic languages based on this result is erroneous. Despite these results, we show by giving a parameterized family that there is a proper hierarchy in k-block deterministic regular languages. We also prove that there is a proper hierarchy in k-lookahead deterministic regular languages by studying particular properties of unary regular expressions. Finally, using our valid results, we confirm that the family of k-block deterministic regular languages is strictly included into the one of k-lookahead deterministic regular languages by showing that any k-block deterministic unary language is one-unambiguous.