On the hierarchy of generalizations of one-unambiguous regular languages
Résumé
A regular language is lookahead (resp. block) deterministic if it is specified by a lookahead (resp. block) deterministic regular expression. These two subclasses of regular languages have been respectively introduced by Han and Wood for lookahead determinism and by Giammarresi et al. for 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 hierarchies and inclusion links of these families. We first show that each block deterministic language is the alphabetical image of some one-unambiguous language. Moreover, we show that deciding the block determinism of a regular language from its minimal DFA does not only require state elimination. Han and Wood state that there is a proper hierarchy in block deterministic languages, but prove it using this erroneous requirement. However, we prove their statement by giving our own parametrized family. We also prove that there is a proper hierarchy in lookahead deterministic languages by studying particular properties of unary regular expressions. Finally, using our valid results, we confirm that the family of block deterministic languages is strictly included in the one of lookahead deterministic languages by showing that any block deterministic unary language is one-unambiguous.