Loading article…
形式言語理論における一般化スター高さ問題とは、すべての正規言語を、クリーネスターのネスト深度が制限された一般化正規表現を用いて表現できるかどうかという未解決問題である。ここで、一般化正規表現は正規表現と同様に定義されるが、補数演算子が組み込まれている。正規言語の場合、その一般化スター高さは、一般化正規表現を用いて言語を記述するために必要なクリーネスターの最小ネスト深度として定義され、これがこの問題の名前の由来となっている。
より具体的には、1を超えるネスト深度が必要かどうか、そして必要であれば、必要な最小星の高さを決定するアルゴリズムが存在するかどうかは未解決の問題である。 [ 1 ]
一般化スターハイトが0の正規言語は、スターフリー言語とも呼ばれる。シュッツェンベルガーの定理は、非周期的な構文モノイドを用いてスターフリー言語の代数的特徴付けを与える。特に、スターフリー言語は正規言語の適切な決定可能な部分クラスである。