通常の言語

理論計算機科学と形式言語理論において、正規言語（有理言語とも呼ばれる）^[1]^{[2]は、理論計算機科学における厳密な意味での}正規表現によって定義できる形式言語である（非正規言語の認識を可能にする機能が拡張された多くの現代の正規表現エンジンとは対照的である）。

あるいは、正規言語は有限オートマトンによって認識される言語として定義される。正規表現と有限オートマトンが同値であることは、クリーネの定理^[3]として知られている（アメリカの数学者スティーブン・コール・クリーネにちなんで）。チョムスキー階層では、正規言語はタイプ3文法によって生成される言語である。

正式な定義

アルファベットΣ上の正規言語の集合は、次のように再帰的に定義されます。

空言語 Ø は通常言語です。
各a ∈ Σ ( a はΣ に属する) に対して、シングルトン言語 { a } は正規言語です。
Aが正規言語であれば、 A * (クリーネスター) は正規言語です。これにより、空文字列言語 {ε} も正規言語になります。
AとB が正規言語である場合、A ∪ B (和集合) とA • B (連結) は正規言語です。
Σ を超える他の言語は正規ではありません。

正規表現の構文とセマンティクスについては、正規表現を参照してください。

例

すべての有限言語は正規です。特に、空の文字列言語 {ε} = Ø* は正規です。他の典型的な例としては、アルファベット { a , b } 上の偶数個のaを含むすべての文字列で構成される言語、またはいくつかのaの後にいくつかのbが続く形式のすべての文字列で構成される言語があります。

正規でない言語の簡単な例としては、文字列の集合 { a ⁿ b ⁿ | n ≥ 0}が挙げられます。 ^[4]直感的には、有限オートマトンではこれを認識できません。有限オートマトンには有限のメモリがあり、a の正確な数を記憶できないためです。この事実を厳密に証明する手法を以下で示します。

同等の形式主義

正規言語は次の同等の特性を満たします。

それは正規表現の言語です（上記の定義による）
これは非決定性有限オートマトン（NFA）によって受け入れられる言語である^[注1]^[注2]
これは決定論的有限オートマトン（DFA）によって受け入れられる言語である^[注3]^[注4]
正規文法によって生成できる^[注5]^[注6]
それは交代有限オートマトンによって受け入れられる言語である
それは双方向有限オートマトンが受け入れる言語である
接頭辞文法によって生成できる
読み取り専用のチューリングマシンで受け入れることができる
これはモナド二階述語論理で定義できる（ビュッヒ・エルゴット・トラクテンブロートの定理）^[5]
これは有限の統語的モノイドMによって認識される。つまり、アルファベット上の自由モノイドからのモノイド準同型f : Σ ^* → Mの下での有限モノイドMの部分集合Sの原像{ w ∈ Σ ^* | f ( w ) ∈ S } である^{[注 7]}
その構文的合同性の同値類の数は有限である。^{[注 8]}^{[注 9] （この数は、}Lを受け入れる最小の決定性有限オートマトンの状態数に等しい。）

特性 10. と 11. は、正規言語を定義するための純粋に代数的なアプローチです。同様の一連のステートメントは、モノイドM ⊆ Σ ^*に対しても定式化できます。この場合、M上の同値性は、認識可能な言語の概念につながります。

一部の著者は、正規言語の代替定義として、上記の「1.」とは異なる特性の 1 つを使用します。

上記の同等性のいくつか、特に最初の 4 つの形式主義の間の同等性は、教科書ではクリーネの定理と呼ばれています。正確にどれ (またはどのサブセット) がそのように呼ばれるかは、著者によって異なります。ある教科書では、正規表現と NFA (上記の「1.」と「2.」) の同等性を「クリーネの定理」と呼んでいます。^[6]別の教科書では、正規表現と DFA (上記の「1.」と「3.」) の同等性を「クリーネの定理」と呼んでいます。^[7]他の 2 つの教科書では、最初に NFA と DFA (「2.」と「3.」) の表現上の同等性を証明し、次に「クリーネの定理」を正規表現と有限オートマトン (後者は「認識可能な言語」を記述すると言われています) の同等性として述べています。^[2]^[8]言語学的なテキストでは、まず正規文法（上記「4.」）をDFAおよびNFAと同一視し、これら（のいずれか）によって生成される言語を「正規」と呼び、その後「有理言語」を表す正規表現を導入し、最後に「クリーネの定理」を正規言語と有理言語の一致として述べています。^[9]他の著者は単に「有理表現」と「正規表現」を同義語として定義し、「有理言語」と「正規言語」についても同様です。^[1]^[2]

どうやら、「正規」という用語は、1951年の技術レポートに由来しており、そこでクリーネは「正規イベント」を導入し、「より説明的な用語に関するあらゆる提案」を明示的に歓迎した。^[10] ノーム・チョムスキーは、1959年の独創的な論文で、最初は「正規」という用語を別の意味で使用していた（今日「チョムスキー標準形」と呼ばれるものを指す）が、^[11]彼の「有限状態言語」がクリーネの「正規イベント」と同等であることに気付いた。^[12]

閉鎖特性

正規言語はさまざまな演算に対して閉じています。つまり、言語KとLが正規言語である場合、次の演算の結果も正規言語になります。

集合論的ブール演算：和集合 $K \cup L$ 、積集合 $K \cap L$ 、補集合 L、したがって相対補集合 $K - L$ 。^[13]
$通常の$ 演算： $K\cupL$ 、連結、 $K\circL$ クリーネスター $L$ $*$ $。$ [ ¹⁴]
3つの演算：文字列準同型、逆文字列準同型、正規言語との交差。結果として、これらは正規言語との商K / Lのように、任意の有限状態変換に対して閉じている。さらに、正規言語は任意の言語との商に対して閉じている。Lが正規言語であれば、任意のKに対してL / Kは正規言語である。^[15]
逆（または鏡像）L ^R。^[16]L を認識する非決定性有限オートマトンが与えられた場合、すべての遷移を逆にし、開始状態と終了状態を入れ替えることで、 L ^Rのオートマトンを得ることができます。これにより、複数の開始状態が発生する可能性がありますが、ε遷移を使用してそれらを結合することができます。

決定可能性特性

2つの決定性有限オートマトンAとBが与えられたとき、それらが同じ言語を受け入れるかどうかは決定可能である。^[17]結果として、上記の閉包特性を用いると、それぞれ受け入れられる言語L _AとL _{B を}持つ任意に与えられた決定性有限オートマトンAとB に対して、以下の問題も決定可能である。

包含: L _A ⊆ L _Bか ? ^{[注 10]}
分離性: L _A ∩ L _B = {}ですか?
空: L _A = {} ですか?
普遍性: L _A = Σ ^*ですか ?
メンバーシップ: a ∈ Σ ^{*が与えられたとき、}a ∈ L _Bですか ?

正規表現の場合、普遍性問題はシングルトンアルファベットに対して既にNP完全である。 ^[18] より大きなアルファベットの場合、その問題はPSPACE完全である。^[19]正規表現を拡張して平方演算子も許可し、「A ^{2 」が「}AA 」と同じことを表す場合でも、正規言語を記述することはできるが、普遍性問題は指数空間の下限を持ち、^[20]^[21]^[22]多項式時間削減に関して指数空間に対して実際完全である。^[23]

固定された有限のアルファベットの場合、すべての言語の集合の理論（文字列、言語における文字列のメンバーシップ、各文字について、文字を文字列に追加する関数（他の操作なし）を含む）は決定可能であり、その最小の基本部分構造は正則言語のみで構成される。2進アルファベットの場合、この理論はS2Sと呼ばれる。^[24]

複雑さの結果

計算複雑性理論では、すべての正規言語の計算複雑性クラスはREGULARまたはREGと呼ばれることもあり、定数空間（使用される空間は入力サイズに依存しない）で解くことができる決定問題であるDSPACE (O(1))に等しい。 REGULAR ≠ AC ⁰である。なぜなら、 REGULAR には（自明に）入力内の 1 ビットの数が偶数か奇数かを決定するパリティ問題が含まれており、この問題はAC ⁰には含まれていないからである。^[25]一方、REGULAR にはAC ⁰が含まれない。なぜなら、回文の非正規言語も非正規言語もAC ⁰で認識できるからである。^[26] $\{0^{n}1^{n}:n\in \mathbb {N} \}$

言語が正規でない場合、それを認識するためには少なくともΩ（log log n）の空間を持つ機械が必要である（nは入力サイズ）。^[27]言い換えれば、DSPACE（o（log log n ））は正規言語のクラスに等しい。実際には、ほとんどの非正規問題は少なくとも対数空間を必要とする機械によって解決される。

チョムスキー階層における位置

チョムスキー階層における正規言語の位置づけは、すべての正規言語が文脈自由言語であることに気づく。逆は真ではない。例えば、文字列のaとbの数が同じである言語は文脈自由言語だが、正規言語ではない。言語が正規言語でないことを証明するために、マイヒル・ネローデ定理とポンピング補題がよく使われる。他のアプローチとしては、正規言語の閉包特性^[28]を使うことや、コルモゴロフ複雑性を定量化することなどがある。^[29]

正規言語の重要なサブクラスには以下が含まれる。

有限言語は、有限の数の単語のみを含む言語です。^[30]これらは正規言語であり、言語内のすべての単語の結合である正規表現を作成できます。
星のない言語、つまり、空記号、文字、連結、および補集合を含むすべてのブール演算子（集合代数を参照）から構成される正規表現で記述できる言語（ただし、クリーネ星は除く）。このクラスにはすべての有限言語が含まれます。^[31]

通常の言語の単語数

の長さの語の数をとします。Lの通常の生成関数は形式的な冪級数です。 $s_{L}(n)$ $n$ $L$

S_{L}(z)=\sum _{n\geq 0}s_{L}(n)z^{n}\ .

言語Lの生成関数は、Lが正則な場合、有理関数である。^[32] したがって、すべての正則言語に対して、シーケンスは定数再帰的である。つまり、任意のに対して長さの単語の数がとなるような整数定数、複素定数、複素多項式が存在する。^[33]^[34]^[35]^[36] $L$ $s_{L}(n)_{n\geq 0}$ $n_{0}$ $\lambda _{1},\,\ldots ,\,\lambda _{k}$ $p_{1}(x),\,\ldots ,\,p_{k}(x)$ $n\geq n_{0}$ $s_{L}(n)$ $n$ $L$ $s_{L}(n)=p_{1}(n)\lambda _{1}^{n}+\dotsb +p_{k}(n)\lambda _{k}^{n}$

このように、ある言語の非正規性は、における与えられた長さの単語を数えることによって証明できる。例えば、バランスのとれた括弧の文字列からなるDyck 言語を考えてみよう。Dyck 言語における長さの単語の数はカタロニア数に等しく、これはという形式ではない。これは Dyck 言語の非正規性を証明している。固有値のいくつかが同じ大きさを持つ可能性もあるので注意が必要である。例えば、すべての偶数二進単語の言語における長さの単語の数はという形式ではないが、偶数または奇数の長さの単語の数はこの形式であり、対応する固有値はである。一般に、すべての正規言語には定数が存在し、すべてのに対して長さの単語の数は漸近的にとなる。^[37] $L'$ $L'$ $2n$ $C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}$ $p(n)\lambda ^{n}$ $\lambda_{i}$ $n$ $p(n)\lambda ^{n}$ $2,-2$ $d$ $a$ $dm+a$ $C_{a}m^{p_{a}}\lambda _{a}^{m}$

言語Lのゼータ関数は^[32]

\zeta _{L}(z)=\exp \left({\sum _{n\geq 0}s_{L}(n){\frac {z^{n}}{n}}} \右）。

正規言語のゼータ関数は一般に有理数ではないが、任意の巡回言語のゼータ関数は有理数である。^[38]^[39]

一般化

正規言語の概念は、無限語（ω-オートマトンを参照）と木（木オートマトンを参照）に一般化されています。

有理集合は、（正規/有理言語という）概念を、必ずしも自由ではないモノイドに一般化します。同様に、（有限オートマトンによる）認識可能言語という概念は、必ずしも自由ではないモノイド上の認識可能集合として同名です。これらの事実に関して、ハワード・シュトラウビングは、「「正規言語」という用語は少し残念です。アイレンバーグのモノグラフ [40] に影響された論文では、オートマトンの動作を指す「認識可能言語」、または正規表現と有理冪級数の間の重要な類似性を指す「有理言語」という用語が頻繁に使用されています。（実際、アイレンバーグは^任意のモノイドの有理および認識可能サブセットを定義していますが、一般的に、この 2 つの概念は一致しません。）この用語は、より意図されたものではあるものの、実際には普及せず、「正規言語」がほぼ普遍的に使用されています。」^{[41] と述べています。}

有理級数は、今度は半環上の形式的な冪級数の文脈におけるもう1つの一般化である。このアプローチにより、重み付き有理式と重み付きオートマトンが生じる。この代数の文脈では、正規言語（ブール重み付き有理式に対応）は通常、有理言語と呼ばれる。^[42]^[43]また、この文脈では、クリーネの定理は、クリーネ-シュッツェンベルガーの定理と呼ばれる一般化を見出す。

事例から学ぶ

注記

^ 1. ⇒ 2.トンプソンの構築アルゴリズムによる
^ 2. ⇒ 1.クリーネのアルゴリズムまたはアーデンの補題を用いて
^ 2. ⇒ 3.べき乗集合構成により
^ 3. ⇒ 2.前者の定義は後者の定義よりも強いため
^ 2. ⇒ 4. ホップクロフト、ウルマン（1979）、定理9.2、p.219を参照
^ 4. ⇒ 2. ホップクロフト、ウルマン（1979）、定理9.1、p.218を参照
^ 3. ≡ 10.マイヒル・ネローデ定理による
^ u ~ vは次のように定義されます: uw ∈ Lであるのは、すべてのw ∈Σ ^*に対してvw ∈ Lである場合のみです。
^ 3. ≡ 11. 証明はSyntactic monoid の記事を参照、またHolcombe, WML (1982) の p.160 を参照。Algebraic automata theory . Cambridge Studies in Advanced Mathematics. Vol. 1. Cambridge University Press . ISBN 0-521-60492-3.ZBL 0489.68046 .
^ L _A ∩ L _B = L _Aであるかどうかを確認します。この特性を決定することは一般にNP 困難です。証明のアイデアの図解については、 File:RegSubsetNP.pdfを参照してください。

参考文献

Berstel, Jean ; Reutenauer, Christophe (2011).非可換有理数級数とその応用. 数学とその応用百科事典. 第137巻. ケンブリッジ:ケンブリッジ大学出版局. ISBN 978-0-521-19022-0.ZBL1250.68007 。
アイレンバーグ、サミュエル(1974)。オートマトン、言語、およびマシン。巻 A。純粋および応用数学。第 58 巻。ニューヨーク: アカデミックプレス。Zbl 0317.94045 。
サロマ、アルト（1981）。形式言語理論の宝石。ピットマン出版。ISBN 0-273-08522-0.ZBL 0487.68064 .
シプサー、マイケル(1997)。計算理論入門。PWS 出版。ISBN 0-534-94728-X.ZBL1169.68300。第 1 章: 正規言語、31 ～ 90 ページ。セクション 4.1: 決定可能言語のサブセクション「正規言語に関する決定可能問題」、152 ～ 155 ページ。
Philippe Flajolet と Robert Sedgewick、「解析的組合せ論: 記号的組合せ論」。オンラインブック、2002 年。
John E. Hopcroft、Jeffrey D. Ullman (1979)。オートマトン理論、言語、計算入門。Addison -Wesley。ISBN 0-201-02988-X。
アルフレッド・V・アホ、ジョン・E・ホップクロフト、ジェフリー・D・ウルマン（1974年）。『コンピュータアルゴリズムの設計と分析』アディソン・ウェスレー。ISBN 9780201000290。

^ ab Ruslan Mitkov (2003). オックスフォード計算言語学ハンドブック. オックスフォード大学出版局. p. 754. ISBN 978-0-19-927634-9。
^ abc マーク・V・ローソン (2003)。有限オートマトン。CRC プレス。pp. 98–103。ISBN 978-1-58488-255-8。
^ 盛裕 (1997)。「常用言語」。グジェゴシュ・ローゼンベルクにて。アルト・サロマー（編）。形式言語ハンドブック: 第 1 巻。単語、言語、文法。スプリンガー。 p. 41.ISBN 978-3-540-60420-4。
^ Eilenberg (1974)、p. 16 (例II、2.8) およびp. 25 (例II、5.2)。
^ M. Weyer: 第 12 章 - S1S と S2S の決定可能性、p. 219、定理 12.26。Erich Grädel、Wolfgang Thomas、Thomas Wilke (編) : オートマトン、ロジック、無限ゲーム: 現在の研究ガイド。Lecture Notes in Computer Science 2500、Springer 2002。
^ ロバート・セジウィック、ケビン・ダニエル・ウェイン (2011)。アルゴリズム。Addison-Wesley Professional。p. 794。ISBN 978-0-321-57351-3。
^ Jean-Paul Allouche、Jeffrey Shallit (2003)。自動シーケンス：理論、アプリケーション、一般化。ケンブリッジ大学出版局。p. 129。ISBN 978-0-521-82332-6。
^ Kenneth Rosen (2011). 離散数学とその応用第7版. McGraw-Hill Science. pp. 873–880.
^ Horst Bunke、Alberto Sanfeliu (1990 年 1 月)。統語的および構造的パターン認識: 理論と応用。World Scientific。p. 248。ISBN 978-9971-5-0566-0。
^ Stephen Cole Kleene (1951 年 12 月)。神経網と有限オートマトンにおけるイベントの表現(PDF) (研究メモ)。米国空軍 / RAND コーポレーション。こちら: p.46
^ ノーム・チョムスキー (1959). 「文法の特定の形式的性質について」(PDF) .情報と制御. 2 (2): 137–167. doi : 10.1016/S0019-9958(59)90362-6 .ここでは、定義8、p.149
^ チョムスキー 1959、脚注 10、p.150
^ サロマ（1981）p.28
^ サロマ（1981）p.27
^ Fellows, Michael R. ; Langston, Michael A. (1991). 「グラフアルゴリズムにおける構成性の問題」。Myers, J. Paul Jr.、O'Donnell, Michael J. (編)。コンピュータサイエンスにおける構成性、サマーシンポジウム、米国テキサス州サンアントニオ、6 月 19 ～ 22 日、議事録。コンピュータサイエンスの講義ノート。第 613 巻。Springer。pp. 150 ～ 158。doi : 10.1007/BFB0021088。ISBN 978-3-540-55631-2。
^ ホップクロフト、ウルマン（1979）、第3章、演習3.4g、p.72
^ ホップクロフト、ウルマン (1979)、定理 3.8、p.64; 定理 3.10、p.67 も参照
^ アホ、ホップクロフト、ウルマン（1974）、演習10.14、p.401
^ アホ、ホップクロフト、ウルマン（1974）、定理10.14、p399
^ ホップクロフト、ウルマン（1979）、定理13.15、p.351
^ AR Meyer & LJ Stockmeyer (1972 年 10 月)。平方化を伴う正規表現の同値問題には指数空間が必要(PDF)。第 13 回 IEEE スイッチングおよびオートマトン理論シンポジウム。pp. 125–129。
^ LJ Stockmeyer; AR Meyer (1973)。「指数時間を必要とする単語問題」。Proc. 5th ann. symp. on Theory of computing (STOC) (PDF)。ACM。pp. 1–9。
^ ホップクロフト、ウルマン（1979）、補遺p.353
^ Weyer, Mark (2002)。「S1S と S2S の決定可能性」。オートマトン、ロジック、無限ゲーム。コンピュータサイエンスの講義ノート。第 2500 巻。Springer。pp. 207–230。doi : 10.1007/3-540-36387-4_12。ISBN 978-3-540-00388-5。
^ Furst, Merrick; Saxe, James B. ; Sipser, Michael (1984). 「パリティ、回路、および多項式時間階層」.数学システム理論. 17 (1): 13–27. doi :10.1007/BF01744431. MR 0738749. S2CID 14677270.
^ クック、スティーブン、グエン、フォン（2010）。論理的基礎の証明の複雑さ（第1版）。ニューヨーク州イサカ：記号論理協会。p. 75。ISBN 978-0-521-51729-4。
^ J. Hartmanis、PL Lewis II、および RE Stearns。メモリ制限計算の階層。スイッチング回路理論とロジック設計に関する第 6 回 IEEE シンポジウムの議事録、pp. 179–190。1965 年。
^ 「言語が正規でないことを証明するには？」cs.stackexchange.com 。 2018年4月10日閲覧。
^ Hromkovič, Juraj (2004). 理論計算機科学: オートマトン、計算可能性、複雑性、アルゴリズム、ランダム化、通信、暗号化入門。Springer。pp. 76–77。ISBN 3-540-14015-8. OCLC 53007120.
^ 有限言語は、有限オートマトンによって生成される（通常は無限の）言語と混同しないでください。
^ Volker Diekert、Paul Gastin (2008)。「第一階定義可能言語」(PDF)。Jörg Flum、Erich Grädel、Thomas Wilke (編)。論理とオートマトン:歴史と展望。アムステルダム大学出版局。ISBN 978-90-5356-576-6。
^ ab Honkala, Juha (1989). 「正規言語のゼータ関数の合理性のための必要条件」. Theor. Comput. Sci . 66 (3): 341–347. doi : 10.1016/0304-3975(89)90159-x . Zbl 0675.68034.
^ Flajolet & Sedgweick、セクションV.3.1、式(13)。
^ 「通常の言語の単語数 $(00)^*$」. cs.stackexchange.com . 2018年4月10日閲覧。
^ 「任意のDFAの定理の証明」。
^ 「通常の言語における特定の長さの単語の数」。cs.stackexchange.com 。 2018年4月10日閲覧。
^ Flajolet & Sedgewick (2002) 定理 V.3
^ ジャン・ベルステル;ロイテナウアー、クリストフ (1990)。「形式言語のゼータ関数」。トランス。午前。数学。社会。321 (2): 533–546。CiteSeerX 10.1.1.309.3005。土井：10.1090/s0002-9947-1990-0998123-x。Zbl 0797.68092。
^ ベルステル＆ロイテナウアー (2011) p.222
^ サミュエル・アイレンバーグ。オートマトン、言語、機械。アカデミック・プレス。2巻「A」（1974年、ISBN 9780080873749）と「B」（1976年、ISBN 9780080873756）で、後者にはブレット・ティルソンによる2章が含まれています。
^ シュトラウビング、ハワード (1994)。有限オートマトン、形式論理、回路の複雑さ。理論計算機科学の進歩。バーゼル:ビルクハウザー。p. 8。ISBN 3-7643-3719-2.ZBL 0816.68086 .
^ ベルステル＆ロイテナウアー (2011) p.47
^ Sakarovitch, Jacques (2009). Elements of automata theory . フランス語からルーベン・トーマスによる翻訳。ケンブリッジ:ケンブリッジ大学出版局。p. 86。ISBN 978-0-521-84425-3.ZBL1188.68177 。

さらに読む

Kleene, SC : 神経網と有限オートマトンにおけるイベントの表現。Shannon, CE、McCarthy, J. (編) Automata Studies、pp. 3–41。プリンストン大学出版局、プリンストン (1956); これは、1951 年のRAND コーポレーションによる同名のレポート RM704 を若干修正したバージョンです。
Sakarovitch, J (1987)。「クリーネの定理の再考」。理論コンピュータサイエンスの動向、技術、および問題。コンピュータサイエンスの講義ノート。第 1987 巻。pp. 39–50。doi : 10.1007 /3540185356_29。ISBN 978-3-540-18535-2。

外部リンク

複雑動物園：クラス REG

[5] 1. ⇒ 2.トンプソンの構築アルゴリズムによる

[6] 2. ⇒ 1.クリーネのアルゴリズムまたはアーデンの補題を用いて

[7] 2. ⇒ 3.べき乗集合構成により

[8] 3. ⇒ 2.前者の定義は後者の定義よりも強いため

[9] 2. ⇒ 4. ホップクロフト、ウルマン（1979）、定理9.2、p.219を参照

[10] 4. ⇒ 2. ホップクロフト、ウルマン（1979）、定理9.1、p.218を参照

[12] 3. ≡ 10.マイヒル・ネローデ定理による

[13] u ~ vは次のように定義されます: uw ∈ Lであるのは、すべてのw ∈Σ ^*に対してvw ∈ Lである場合のみです。

[14] 3. ≡ 11. 証明はSyntactic monoid の記事を参照、またHolcombe, WML (1982) の p.160 を参照。Algebraic automata theory . Cambridge Studies in Advanced Mathematics. Vol. 1. Cambridge University Press . ISBN 0-521-60492-3.ZBL 0489.68046 .

[27] L _A ∩ L _B = L _Aであるかどうかを確認します。この特性を決定することは一般にNP 困難です。証明のアイデアの図解については、 File:RegSubsetNP.pdfを参照してください。

[Mitkov2003-1] Ruslan Mitkov (2003). オックスフォード計算言語学ハンドブック. オックスフォード大学出版局. p. 754. ISBN 978-0-19-927634-9。

[Lawson2003-2] マーク・V・ローソン (2003)。有限オートマトン。CRC プレス。pp. 98–103。ISBN 978-1-58488-255-8。

[RozenbergSalomaa1997-3] 盛裕 (1997)。「常用言語」。グジェゴシュ・ローゼンベルクにて。アルト・サロマー（編）。形式言語ハンドブック: 第 1 巻。単語、言語、文法。スプリンガー。 p. 41.ISBN 978-3-540-60420-4。

[4] Eilenberg (1974)、p. 16 (例II、2.8) およびp. 25 (例II、5.2)。

[11] M. Weyer: 第 12 章 - S1S と S2S の決定可能性、p. 219、定理 12.26。Erich Grädel、Wolfgang Thomas、Thomas Wilke (編) : オートマトン、ロジック、無限ゲーム: 現在の研究ガイド。Lecture Notes in Computer Science 2500、Springer 2002。

[SedgewickWayne2011-15] ロバート・セジウィック、ケビン・ダニエル・ウェイン (2011)。アルゴリズム。Addison-Wesley Professional。p. 794。ISBN 978-0-321-57351-3。

[AlloucheShallit2003-16] Jean-Paul Allouche、Jeffrey Shallit (2003)。自動シーケンス：理論、アプリケーション、一般化。ケンブリッジ大学出版局。p. 129。ISBN 978-0-521-82332-6。

[Rosen2011-17] Kenneth Rosen (2011). 離散数学とその応用第7版. McGraw-Hill Science. pp. 873–880.

[BunkeSanfeliu1990-18] Horst Bunke、Alberto Sanfeliu (1990 年 1 月)。統語的および構造的パターン認識: 理論と応用。World Scientific。p. 248。ISBN 978-9971-5-0566-0。

[19] Stephen Cole Kleene (1951 年 12 月)。神経網と有限オートマトンにおけるイベントの表現(PDF) (研究メモ)。米国空軍 / RAND コーポレーション。こちら: p.46

[Chomsky.1959a-20] ノーム・チョムスキー (1959). 「文法の特定の形式的性質について」(PDF) .情報と制御. 2 (2): 137–167. doi : 10.1016/S0019-9958(59)90362-6 .ここでは、定義8、p.149

[21] チョムスキー 1959、脚注 10、p.150

[Sal28-22] サロマ（1981）p.28

[Sal27-23] サロマ（1981）p.27

[24] Fellows, Michael R. ; Langston, Michael A. (1991). 「グラフアルゴリズムにおける構成性の問題」。Myers, J. Paul Jr.、O'Donnell, Michael J. (編)。コンピュータサイエンスにおける構成性、サマーシンポジウム、米国テキサス州サンアントニオ、6 月 19 ～ 22 日、議事録。コンピュータサイエンスの講義ノート。第 613 巻。Springer。pp. 150 ～ 158。doi : 10.1007/BFB0021088。ISBN 978-3-540-55631-2。

[25] ホップクロフト、ウルマン（1979）、第3章、演習3.4g、p.72

[26] ホップクロフト、ウルマン (1979)、定理 3.8、p.64; 定理 3.10、p.67 も参照

[28] アホ、ホップクロフト、ウルマン（1974）、演習10.14、p.401

[29] アホ、ホップクロフト、ウルマン（1974）、定理10.14、p399

[30] ホップクロフト、ウルマン（1979）、定理13.15、p.351

[31] AR Meyer & LJ Stockmeyer (1972 年 10 月)。平方化を伴う正規表現の同値問題には指数空間が必要(PDF)。第 13 回 IEEE スイッチングおよびオートマトン理論シンポジウム。pp. 125–129。

[32] LJ Stockmeyer; AR Meyer (1973)。「指数時間を必要とする単語問題」。Proc. 5th ann. symp. on Theory of computing (STOC) (PDF)。ACM。pp. 1–9。

[33] ホップクロフト、ウルマン（1979）、補遺p.353

[34] Weyer, Mark (2002)。「S1S と S2S の決定可能性」。オートマトン、ロジック、無限ゲーム。コンピュータサイエンスの講義ノート。第 2500 巻。Springer。pp. 207–230。doi : 10.1007/3-540-36387-4_12。ISBN 978-3-540-00388-5。

[35] Furst, Merrick; Saxe, James B. ; Sipser, Michael (1984). 「パリティ、回路、および多項式時間階層」.数学システム理論. 17 (1): 13–27. doi :10.1007/BF01744431. MR 0738749. S2CID 14677270.

[36] クック、スティーブン、グエン、フォン（2010）。論理的基礎の証明の複雑さ（第1版）。ニューヨーク州イサカ：記号論理協会。p. 75。ISBN 978-0-521-51729-4。

[37] J. Hartmanis、PL Lewis II、および RE Stearns。メモリ制限計算の階層。スイッチング回路理論とロジック設計に関する第 6 回 IEEE シンポジウムの議事録、pp. 179–190。1965 年。

[38] 「言語が正規でないことを証明するには？」cs.stackexchange.com 。 2018年4月10日閲覧。

[39] Hromkovič, Juraj (2004). 理論計算機科学: オートマトン、計算可能性、複雑性、アルゴリズム、ランダム化、通信、暗号化入門。Springer。pp. 76–77。ISBN 3-540-14015-8. OCLC 53007120.

[40] 有限言語は、有限オートマトンによって生成される（通常は無限の）言語と混同しないでください。

[41] Volker Diekert、Paul Gastin (2008)。「第一階定義可能言語」(PDF)。Jörg Flum、Erich Grädel、Thomas Wilke (編)。論理とオートマトン:歴史と展望。アムステルダム大学出版局。ISBN 978-90-5356-576-6。

[Honkala-42] Honkala, Juha (1989). 「正規言語のゼータ関数の合理性のための必要条件」. Theor. Comput. Sci . 66 (3): 341–347. doi : 10.1016/0304-3975(89)90159-x . Zbl 0675.68034.

[43] Flajolet & Sedgweick、セクションV.3.1、式(13)。

[44] 「通常の言語の単語数 $(00)^*$」. cs.stackexchange.com . 2018年4月10日閲覧。

[45] 「任意のDFAの定理の証明」。

[46] 「通常の言語における特定の長さの単語の数」。cs.stackexchange.com 。 2018年4月10日閲覧。

[47] Flajolet & Sedgewick (2002) 定理 V.3

[48] ジャン・ベルステル;ロイテナウアー、クリストフ (1990)。「形式言語のゼータ関数」。トランス。午前。数学。社会。321 (2): 533–546。CiteSeerX 10.1.1.309.3005。土井：10.1090/s0002-9947-1990-0998123-x。Zbl 0797.68092。

[49] ベルステル＆ロイテナウアー (2011) p.222

[Eilenberg1974-50] サミュエル・アイレンバーグ。オートマトン、言語、機械。アカデミック・プレス。2巻「A」（1974年、ISBN 9780080873749）と「B」（1976年、ISBN 9780080873756）で、後者にはブレット・ティルソンによる2章が含まれています。

[51] シュトラウビング、ハワード (1994)。有限オートマトン、形式論理、回路の複雑さ。理論計算機科学の進歩。バーゼル:ビルクハウザー。p. 8。ISBN 3-7643-3719-2.ZBL 0816.68086 .

[52] ベルステル＆ロイテナウアー (2011) p.47

[53] Sakarovitch, Jacques (2009). Elements of automata theory . フランス語からルーベン・トーマスによる翻訳。ケンブリッジ:ケンブリッジ大学出版局。p. 86。ISBN 978-0-521-84425-3.ZBL1188.68177 。