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:
“Find out the peaceful hermitage,
The hairy gown and mossy cell,
Where I may sit and rightly spell
Of every star that heaven doth show,
And every herb that sips the dew;
Till old experience do attain
To something like prophetic strain.
These pleasures Melancholy give,
And I with thee will choose to live.”
—John Milton (1608–1674)
“Men often treat others worse than they treat themselves, but they rarely treat anyone better. It is the height of folly to expect consideration and decency from a person who mistreats himself.”
—Thomas Szasz (b. 1920)
“Theology, I am persuaded, derives its initial impulse from a religious wavering; for there is quite as much, or more, that is mysterious and calculated to awaken scientific curiosity in the intercourse with God, and it [is] a problem quite analogous to that of theology.”
—Charles Sanders Peirce (1839–1914)