display | more...
If we only use regular expressions with a limited nesting depth of Kleene stars, are there regular languages we cannot express?

Specifically, is a nesting depth of more than 2 required? If so, can we determine how many are required?

This theoretical problem remained open for 30 years, to be solved by Kosaburu Hashiguchi in 1983. The answers are yes, yes, and yes.

However, for regular expression with complementation, in which we can write things like

  !(a u ab)*

the star height problem is still open; for details see

Log in or register to write something here or to contact authors.