正規言語

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

理論計算機科学形式言語理論では正規言語(合理言語とも呼ばれます[1] [2]は、理論計算機科学の厳密な意味で(とは対照的に)正規表現で定義できる形式言語です。多くの最新の正規表現エンジンは、非正規言語の認識を可能に する機能で強化されています)。

あるいは、正規言語は、有限オートマトンによって認識される言語として定義できます正規表現と有限オートマトンの等価性は、Kleeneの定理[3]として知られています(アメリカの数学者Stephen Cole Kleeneにちなんで)。チョムスキー階層では、正規言語はタイプ3文法によって生成される言語です。

正式な定義

アルファベットΣ上の正規言語のコレクションは、次のように再帰的に定義されます。

  • 空の言語Øは正規言語です。
  • a∈Σ(aはΣ属する)について、シングルトン言語{ a }は正規言語です。
  • Aが正規言語の場合、 A *(クリーネ閉包)は正規言語です。このため、空の文字列言語{ε}も通常です。
  • ABが正規言語の場合、A∪B(和集合)とAB 連結正規言語です。
  • Σを超える他の言語は規則的ではありません。

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

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

規則的ではない言語の簡単な例は、文字列のセット{ a n b n | n≥0 }。[4]直感的には、有限オートマトンは有限のメモリを持ち、aの正確な数を記憶できないため、有限オートマトンでは認識できません。この事実を厳密に証明するための手法を以下に示します

同等の形式

正規言語は、次の同等のプロパティを満たします。

  1. これは正規表現の言語です(上記の定義による)
  2. これは、非決定性有限オートマトン(NFA)によって受け入れられる言語です[注1] [注2]
  3. これは、決定性有限オートマトン(DFA)によって受け入れられる言語です[注3] [注4]
  4. 正規文法で生成できます[注5] [注6]
  5. これは、交互の有限オートマトンによって受け入れられる言語です。
  6. これは、双方向有限オートマトンによって受け入れられる言語です。
  7. 接頭辞文法で生成できます
  8. 読み取り専用のチューリングマシンで受け入れることができます
  9. これは、モナディック 2次論理Büchi–Elgot–Trakhtenbrotの定理で定義できます[5]。
  10. これは、有限の構文モノイドMによって認識されます。つまり、プレイメージ{ w∈Σ * | アルファベットの自由モノイドからのモノイド準同型f:Σ *Mの下での有限モノイドMの部分集合Sのfw)∈S } [注7]
  11. その構文合同の同値類の数は有限です。[注8] [注9] (この数は、 Lを受け入れる最小決定性有限オートマトンの状態の数に等しくなります。)

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

一部の作成者は、「1」とは異なる上記のプロパティの1つを使用します。正規言語の代替定義として。

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

どうやら、「通常」という用語は、Kleeneが「定期的なイベント」を紹介し、「より説明的な用語に関する提案」を明示的に歓迎した1951年のテクニカルレポートに由来しているようです。[10] ノーム・チョムスキーは、1959年の独創的な記事で、最初は「通常」という用語を別の意味で使用していました(今日はチョムスキー標準形と呼ばれるものを指します)[11]が、彼の「有限状態言語」に気づきました。 Kleeneの「定期的なイベント」と同等でした。[12]

クロージャのプロパティ

正規言語は、さまざまな操作で閉じられます。つまり、言語KLが正規である場合、次の操作の結果です。

  • 集合論的ブール演算和集合 K∪L共通部分K∩L および集合Lしたがって相対集合K −L[13]
  • 通常の操作K∪L連結 、およびクリーネ閉包 L *[14]
  • トリオ操作:文字列準同型逆文字列準同型、および正規言語との共通部分。結果として、それらは 、正規言語のK / Lのように、任意の有限状態変換の下で閉じられます。さらに、正規言語は任意の言語の商の下で閉じられます。Lが正規である場合、 L / Kは任意のKに対して正規です。[要出典]
  • (または鏡像)LR[15] Lを認識する非決定性有限オートマトンが与えられた場合、L Rのオートマトンは、すべての遷移を反転し、開始状態と終了状態を交換することによって取得できます。これにより、複数の開始状態が発生する可能性があります。ε遷移を使用してそれらを結合できます。

決定可能性のプロパティ

2つの決定性有限オートマトンABが与えられると、それらが同じ言語を受け入れるかどうかを決定できます。[16] 結果として、上記の閉包特性を使用して、受け入れられ言語LAおよびLBを使用して、任意に与えられた決定性有限オートマトンAおよびBについて、次の問題も決定可能です

  • 封じ込め :LA⊆LBですか_ _ 【注10】
  • 整合:LA∩LB = { }
  • 空:L A = {}?
  • 普遍性:L A*  ?
  • メンバーシップa∈Σ *が与えられ 場合 a∈LB

正規表現の場合、普遍性の問題は、シングルトンアルファベットのNP完全問題です。[17] 大きなアルファベットの場合、その問題はPSPACE-completeです。[18]正規表現を拡張して二乗演算子も使用できるようにすると、「A 2 」は「 AA 」と同じ意味になりますが、それでも正規言語だけを記述できますが、普遍性の問題には指数空間の下限があります[19]。[20] [21]であり、実際には、多項式時間変換に関する指数空間については完全です。[22]

複雑さの結果

計算の複雑さの理論では、すべての正規言語の複雑さのクラスはREGULARまたはREGと呼ばれることがあり、 DSPACE(O(1))に等しくなります。これは、一定の空間で解決できる決定問題です(使用される空間は入力サイズに依存しません)。 )。REGULARAC0 これは、入力の1ビット数が偶数か奇数かを判断するパリティ問題が(自明に)含まれており、この問題がAC0にないためです[23]一方、REGULARにはAC0は含まれていません回文の非正規言語、または非正規言語のため両方ともAC0で認識できます[24]

言語が規則的でない場合、認識するために少なくともΩ(log log n)スペースを持つマシンが必要です(nは入力サイズです)。[25]言い換えると、DSPACE(o(log log n))は正規言語のクラスと同じです。実際には、ほとんどの非規則的な問題は、少なくとも対数空間をとるマシンによって解決されます。

チョムスキー階層内の場所

チョムスキー階層のクラスの正規言語。

チョムスキー階層で正規言語を見つけるために、すべての正規言語が文脈自由であることに気づきます。逆は当てはまりません。たとえば、bと同じ数のaを持つすべての文字列で構成される言語は、文脈自由ですが、規則的ではありません。言語が規則的でないことを証明するために、マイヒル-ネロードの定理と正規言語の反復補題をよく使用します。他のアプローチには、正規言語のクロージャープロパティの使用[26]や、コルモゴロフ複雑度の定量化が含まれます[27]

正規言語の重要なサブクラスには次のものがあります

正規言語の単語数

させて長さの単語数を示しますL通常の母関数形式的べき級数です。

Lが正規である場合、言語Lの母関数は有理関数です。[30] したがって、すべての正規言語についてシーケンス定数-再帰的です; つまり、整数定数が存在します、複素定数および複素多項式 そのようなすべてのために人数、個数、総数長さの言葉の[31] [32] [33] [34]

したがって、特定の言語の不規則性で与えられた長さの単語を数えることによって証明することができます たとえば、バランスの取れた括弧の文字列のディック言語を考えてみましょう。長さの単語数ディック言語ではカタラン数 に等しい 、形式ではありません、ディック言語の不規則性を目撃しました。一部の固有値があるため、注意が必要です。同じ大きさを持つことができます。たとえば、長さの単語の数すべてのバイナリワードの言語では、形式ではありません、ただし、偶数または奇数の長さの単語の数はこの形式です。対応する固有値は次のとおりです。一般に、すべての正規言語には定数が存在しますすべての人のために、長さの単語数漸近的です[35]

言語Lゼータ関数[30]です。

正規言語のゼータ関数は一般に有理数ではありませんが、任意の循環言語のゼータ関数は有理数です。[36] [37]

一般化

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

Rationalセットは、(正規/合理的な言語の)概念を必ずしも無料ではないモノイドに一般化します。同様に、(有限オートマトンによる)認識可能な言語の概念には、必ずしも自由ではないモノイド上の認識可能なセットとしての名前が付けられています。ハワード・ストラウビングは、これらの事実に関連して、「「正規言語」という用語は少し残念です。アイレンバーグのモノグラフに影響を受けた論文[38]多くの場合、オートマトンの動作を指す「認識可能な言語」、または正規表現と合理的なべき級数の間の重要な類似性を指す「合理的な言語」のいずれかを使用します。(実際、Eilenbergは、任意のモノイドの合理的で認識可能なサブセットを定義しています。2つの概念は、一般に一致しません。)この用語は、やる気はありますが、実際には理解されておらず、「正規言語」はほぼ普遍的に使用されています。」[39]

有理級数は別の一般化であり、今回は半環上の形式的べき級数の文脈で。このアプローチにより、加重有理式加重オートマトンが生成されます。この代数の文脈では、正規言語(ブール加重有理式に対応)は通常、有理言語と呼ばれます。[40] [41]また、この文脈において、Kleeneの定理は、 Kleene-Schützenbergerの定理と呼ばれる一般化を見つけます。

例から学ぶ

メモ

  1. ^ 1.⇒2。トンプソンの構築アルゴリズムによる
  2. ^ 2.⇒1。KleeneのアルゴリズムまたはArdenの補題を使用
  3. ^ 2.⇒3。パワーセット構造による
  4. ^ 3.⇒2。前者の定義後者よりも強いので
  5. ^ 2.⇒4。Hopcroft、Ullman(1979)、定理9.2、p.219を参照してください。
  6. ^ 4.⇒2。Hopcroft、Ullman(1979)、定理9.1、p.218を参照してください。
  7. ^ 3.⇔10 。マイヒル-ネロードの定理による
  8. ^ u〜vは、ように定義されます。すべてのw∈Σ*に対してvw∈Lある場合限り、 uw∈L
  9. ^ 3.⇔11。 構文モノイドの記事の証明を参照してください。また、 Holcombe、WML(1982)のp.160を参照してください代数オートマトン理論高度な数学におけるケンブリッジ研究。1.ケンブリッジ大学出版局ISBN 0-521-60492-3Zbl0489.68046 _
  10. ^ LA∩LB = LAどうを確認ますこのプロパティの決定は、一般的にNP困難です。証明のアイデアの図については、 File:RegSubsetNP.pdfを参照

参考文献

  1. ^ a b Ruslan Mitkov(2003)。計算言語学のオックスフォードハンドブックオックスフォード大学出版局。p。754. ISBN 978-0-19-927634-9
  2. ^ a b c マーク・V・ローソン(2003)。有限オートマトンCRCプレス。pp。98–103。ISBN 978-1-58488-255-8
  3. ^ Sheng Yu(1997)。「正規言語」GrzegorzRozenbergでは; Arto Salomaa(編)。形式言語ハンドブック:第1巻。単語、言語、文法スプリンガー。p。41. ISBN 978-3-540-60420-4
  4. ^ Eilenberg(1974)、p。16(例II、2.8)およびp。25(例II、5.2)。
  5. ^ M. Weyer:第12章-S1SおよびS2Sの決定可能性、p。219、定理12.26。In:ErichGrädel、Wolfgang Thomas、Thomas Wilke(編):Automata、Logics、およびInfinite Games:現在の研究へのガイド。コンピュータサイエンス2500、Springer2002の講義ノート。
  6. ^ ロバートセッジウィック; ケビンダニエルウェイン(2011)。アルゴリズムアディソン-ウェスリープロフェッショナル。p。794. ISBN 978-0-321-57351-3
  7. ^ Jean-Paul Allouche; ジェフリー・シャリット(2003)。自動シーケンス:理論、アプリケーション、一般化ケンブリッジ大学出版局。p。129. ISBN 978-0-521-82332-6
  8. ^ ケネスローゼン(2011)。離散数学とその応用第7版マグロウヒルサイエンス。pp。873–880。
  9. ^ ホースト・ブンケ; アルベルトサンフェリウ(1990年1月)。構文的および構造的パターン認識:理論と応用世界科学。p。248. ISBN 978-9971-5-0566-0
  10. ^ スティーブンコールクリーン(1951年12月)。神経網と有限自動化におけるイベントの表現(PDF)(研究覚書)。アメリカ空軍/ランド研究所。 こちら:p.46
  11. ^ ノーム・チョムスキー(1959)。「文法の特定の形式的特性について」(PDF)情報と管理2(2):137–167。土井10.1016 / S0019-9958(59)90362-6 ここで:定義8、p.149
  12. ^ チョムスキー1959、脚注10、p.150
  13. ^ Salomaa(1981)p.28
  14. ^ Salomaa(1981)p.27
  15. ^ ホップクロフト、ウルマン(1979)、第3章、演習3.4g、p。72
  16. ^ ホップクロフト、ウルマン(1979)、定理3.8、p.64; 定理3.10、p.67も参照してください。
  17. ^ Aho、Hopcroft、Ullman(1974)、演習10.14、p.401
  18. ^ Aho、Hopcroft、Ullman(1974)、定理10.14、p399
  19. ^ ホップクロフト、ウルマン(1979)、定理13.15、p.351
  20. ^ AR Meyer&LJ Stockmeyer(1972年10月)。二乗を伴う正規表現の等価問題には指数空間が必要です(PDF)第13回年次IEEE症状。スイッチングとオートマトン理論についてpp。125–129。
  21. ^ LJストックマイヤー&ARメイヤー(1973)。指数関数的な時間を必要とする文章題(PDF)Proc。5アン。症状。計算理論(STOC)についてACM。pp。1–9。
  22. ^ ホップクロフト、ウルマン(1979)、結果p.353
  23. ^ ファースト、メリック; Saxe、James B .; シプサ、マイケル(1984)。「パリティ、回路、および多項式時間階層」。数学システム理論17(1):13–27。土井10.1007 / BF01744431MR0738749_ S2CID14677270_  
  24. ^ クック、スティーブン; グエン、フォン(2010)。証明の複雑さの論理的基礎(1.publ。ed。)ニューヨーク州イサカ:シンボリックロジック協会。p。75. ISBN 978-0-521-51729-4
  25. ^ J. Hartmanis、PL Lewis II、およびREStearns。メモリが制限された計算の階層。スイッチング回路理論と論理設計に関する第6回IEEEシンポジウムの議事録、 179〜190ページ。1965年。
  26. ^ 「言語が規則的でないことを証明する方法は?」cs.stackexchange.com 2018年4月10日取得
  27. ^ Hromkovič、Juraj(2004)。理論計算機科学:オートマトン、計算可能性、複雑さ、アルゴリズム、ランダム化、通信、および暗号化の概要スプリンガー。pp。76–77。ISBN 3-540-14015-8OCLC53007120 _
  28. ^ 有限言語は、有限オートマトンによって生成された(通常は無限の)言語と混同しないでください。
  29. ^ Volker Diekert; ポール・ガスティン(2008)。「一次定義可能な言語」(PDF)ヨルグ・フルム; ErichGrädel; トーマス・ウィルケ(編)。ロジックとオートマトン:歴史と展望アムステルダム大学出版局。ISBN  978-90-5356-576-6
  30. ^ a b Honkala、Juha(1989)。「正規言語のゼータ関数の合理性に必要な条件」理論。計算します。科学66(3):341–347。土井10.1016 / 0304-3975(89)90159-xZbl0675.68034_ 
  31. ^ Flajolet&Sedgweick、セクションV.3.1、式(13)。
  32. ^ "正規言語の単語数$(00)^ * $"cs.stackexchange.com 2018年4月10日取得
  33. ^ 「任意のDFAの定理の証明」
  34. ^ 「正規言語で指定された長さの単語の数」cs.stackexchange.com 2018年4月10日取得
  35. ^ フラジョレ&セッジウィック(2002)定理V.3
  36. ^ ベルステル、ジャン; ロイテナウアー、クリストフ(1990)。「形式言語のゼータ関数」。トランス。午前。算数。Soc321(2):533–546。CiteSeerX10.1.1.309.3005_ 土井10.1090 / s0002-9947-1990-0998123-xZbl0797.68092_  
  37. ^ Berstel&Reutenauer(2011)p.222
  38. ^ サミュエル・アイレンバーグ。Automata、言語、およびマシンアカデミックプレス。2巻の「A」(1974、ISBN 9780080873749)と「B」(1976、ISBN 9780080873756)で、後者にはBretTilsonによる2つの章があります。  
  39. ^ シュトラウビング、ハワード(1994)。有限オートマトン、形式論理、および回路の複雑さ理論計算機科学の進歩。バーゼル:ビルクホイザー。p。 8ISBN 3-7643-3719-2Zbl0816.68086 _
  40. ^ Berstel&Reutenauer(2011)p.47
  41. ^ Sakarovitch、Jacques(2009)。オートマトン理論の要素ReubenThomasによるフランス語からの翻訳。ケンブリッジ:ケンブリッジ大学出版局p。86. ISBN 978-0-521-84425-3Zbl1188.68177 _

さらに読む

  • Kleene、SC:神経網と有限オートマトンのイベントの表現。In:Shannon、CE、McCarthy、J。(eds。)Automata Studies、pp。3–41。プリンストン大学出版局、プリンストン(1956); これは、同じタイトルの彼の1951 RANDCorporationレポートRM704のわずかに変更されたバージョンです
  • サカロビッチ、J(1987)。「クリーネの定理の再考」。理論計算機科学の動向、技術、および問題コンピュータサイエンスの講義ノート。1987. pp。39–50。土井10.1007 / 3540185356_29ISBN 978-3-540-18535-2

外部リンク