Star height problem とは

正式な言語理論における星の高さの問題は、全ての規則的な言語が、制限された星の高さの正規表現を使用して、すなわちクレーンの星の限定されたネスティング深さで表現できるかどうかという問題である。具体的には、入れ子の深さは1で十分ですか?そうでない場合、必要な数を決定するアルゴリズムはありますか?この問題はEggan(1963)によって提起された。