The infinite 2-star height hierarchy of extended regular languages of star degree at most two (Q1341774)

The concept of regular expressions and their equivalence to regular languages is well-known. The operation of 2-star (an extension of Kleene star as used in regular expressions), and the corresponding class of extended regular expressions, were introduced by the author and H. Yoo in 1990. The extended regular expressions define a superclass of regular languages and a proper subclass of context-free languages. In this paper the author defines the concept of 2-star height (again, in analogy to star height of regular expressions), and proves that the resulting height-hierarchy is infinite.