星のない言語

理論計算機科学と形式言語理論では、正規言語は、アルファベットの文字、空語、空集合記号、すべてのブール演算子（補数を含む）、連結で構成され、クリーネスターを含まない正規表現で記述できる場合、スターフリーであると言われます。^{[1]この条件は、}一般化されたスターの高さがゼロであることと同等です。

たとえば、アルファベット上のすべての有限語の言語は、空集合 の補集合 を取ることによって星なしであることが示されます。次に、連続する a を持たないアルファベット上の語の言語はと定義できます。これは、最初に任意の接頭辞と接尾辞を持つ からなる語の言語を構築し、次にその補集合 (部分文字列 を含まないすべての語でなければなりません) を取ることによって行われます。 ${\displaystyle \Sigma^{*}}$${\displaystyle \Sigma }$${\displaystyle \Sigma ^{*}={\bar {\emptyset }}}$${\displaystyle \{a,\,b\}}$${\displaystyle {\overline {\Sigma ^{*}aa\Sigma ^{*}}}}$${\displaystyle aa}$${\displaystyle aa}$

星なしではない正規言語の例としては、^{[2] 、}つまり偶数個の「a」からなる文字列の言語があります。 の場合、言語は、すべての単語の集合から で始まる単語、 で終わる単語、またはを含む単語を取り除いたとして定義できます。ただし、 の場合、この定義では は作成されません 。 ${\displaystyle (aa)^{*}}$${\displaystyle (ab)^{*}}$${\displaystyle a\neq b}$${\displaystyle \Sigma ^{*}\setminus (b\Sigma ^{*}\cup \Sigma ^{*}a\cup \Sigma ^{*}aa\Sigma ^{*}\cup \Sigma ^{*}bb\Sigma ^{*})}$${\displaystyle b}$${\displaystyle a}$${\displaystyle aa}$${\displaystyle bb}$${\displaystyle a=b}$${\displaystyle (aa)^{*}}$

マルセル＝ポール・シュッツェンベルガーは、スターフリー言語を非周期的 統語的モノイドを持つ言語として特徴づけた。^{[3] [4]}また、それらは、FO[<] （小なり関係を持つ自然数上の一階述語論理） で定義可能な言語として論理的に特徴づけられる。 ^[5]カウンターフリー言語^[6]および線形時相論理で定義可能な言語として特徴づけられる。^[7]

星のない言語はすべて均一なAC ⁰です。

• 星の高さ
• 星の高さの問題
• 一般化された星の高さの問題

• ローソン、マーク V. (2004)。有限オートマトン。チャップマン＆ホール/CRC。ISBN 1-58488-255-7.ZBL1086.68074  。​
• Diekert, Volker; Gastin, Paul (2008)。「第一階定義可能言語」。Jörg Flum、Erich Grädel、Thomas Wilke (編)。論理とオートマトン: 歴史と展望(PDF)。アムステルダム大学出版局。ISBN 978-90-5356-576-6。