正規文法とは? わかりやすく解説

Weblio 辞書 > 同じ種類の言葉 > 言葉 > 文法 > 文法 > 正規文法の意味・解説 

正規文法

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/05/09 14:47 UTC 版)

正規文法(せいきぶんぽう、: regular grammar)は、形式文法における右正規文法(みぎせいきぶんぽう、: right-regular grammar)と左正規文法(ひだりせいきぶんぽう、: left-regular grammar)の総称。

右正規文法は、形式文法 (N, Σ, P, S) において P に含まれる生成規則が以下のような形式になっているものである。

  1. Aa
  2. AaB
  3. A → ε

ここで、ABSN非終端記号a ∈ Σ は終端記号、ε は空文字列S は開始記号である。

左正規文法は、生成規則が次の形式に従う。

  1. Aa
  2. ABa
  3. A → ε

右正規文法 G の例を示す。G は、N = {S, A}、Σ = {a, b, c} から構成され、P には以下の規則がある。

SaS
SbA
A → ε
AcA

S は開始記号である。この文法を等価な正規表現で表すと a*bc* となる。

概要

正規文法は全ての正規言語を記述することができ、そういう意味では有限オートマトン正規表現と等価である。さらに言えば、右正規文法も左正規文法も同じ正規言語を定義することができる。

正規文法は全て文脈自由文法に含まれる。

全ての文脈自由文法は、左正規規則と右正規規則の組み合わせに容易に変換可能である。つまり、右正規文法と左正規文法を合成することで全ての文脈自由言語を表現可能である。正規文法は左正規規則か右正規規則を使用するが、同時に両者を使用することはない。そのため、より狭い範囲の言語である正規言語だけを記述できる。

正規文法に空文字列(ε)を許さない場合もある。

関連項目





正規文法と同じ種類の言葉


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「正規文法」の関連用語

正規文法のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



正規文法のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの正規文法 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS