regular expressions


Star height problem ★★

Author(s): Lawrence Eggan C.

Conjecture   The star height problem in formal language theory is the question whether all regular languages can be expressed using regular expressions of limited star height, i.e. with a limited nesting depth of Kleene stars. Specifically, is a nesting depth of one always sufficient? If not, is there an algorithm to determine how many are required?

Keywords: formal language; Kleene stars; regular expressions; regular languages

Syndicate content