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:
“Between us two it’s not a star at all.
It’s a new patented electric light,
Put up on trial by that Jerseyite
So much is being now expected of....”
—Robert Frost (1874–1963)
“To say more than human things with human voice,
That cannot be; to say human things with more
Than human voice, that, also, cannot be;
To speak humanly from the height or from the depth
Of human things, that is acutest speech.”
—Wallace Stevens (1879–1955)
“We have heard all of our lives how, after the Civil War was over, the South went back to straighten itself out and make a living again. It was for many years a voiceless part of the government. The balance of power moved away from it—to the north and the east. The problems of the north and the east became the big problem of the country and nobody paid much attention to the economic unbalance the South had left as its only choice.”
—Lyndon Baines Johnson (1908–1973)