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? The problem was raised by Eggan (1963).
Read more about Star Height Problem: Families of Regular Languages With Unbounded Star Height, Computing The Star Height of Regular Languages
Famous quotes containing the words star, height and/or problem:
“One thing about being successful is that I stopped being afraid of dying. Once you’re a star you’re dead already. You’re embalmed.”
—Dustin Hoffman (b. 1937)
“How frightening it is to have reached the height of human accomplishment in art that must forever borrow from life’s abundance.”
—Franz Grillparzer (1791–1872)
“Only in the problem play is there any real drama, because drama is no mere setting up of the camera to nature: it is the presentation in parable of the conflict between Man’s will and his environment: in a word, of problem.”
—George Bernard Shaw (1856–1950)