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:
“The sun descending in the west,
The evening star does shine;
The birds are silent in their nest,
And I must seek for mine.”
—William Blake (1757–1827)
“I cannot help wondering sometimes what I might have become and might have done if I had lived in a country which had not circumscribed and handicapped me on account of my race, but had allowed me to reach any height I was able to attain.”
—Mary Church Terrell (1863–1954)
“In the nineteenth century the problem was that God is dead; in the twentieth century the problem is that man is dead.”
—Erich Fromm (1900–1980)