正規文法
出典: フリー百科事典『ウィキペディア（Wikipedia）』
情報工学における右正規文法（みぎせいきぶんぽう、Right Regular Grammar）は、形式文法(N, Σ, P, S) において P に含まれる生成規則が以下のような形式になっているものである。
- A → a - ここで A は N に含まれる非終端記号で、a は Σ に含まれる終端文字である。
- A → aB - ここで A と B は N に含まれ、a は Σ に含まれる。
- A → ε - ここで A は N に含まれる。
左正規文法（ひだりせいきぶんぽう、Left Regular Grammar）は、以下の規則に従う。
- A → a - ここで A は N に含まれる非終端記号であり、a は Σ に含まれる終端文字である。
- A → Ba - ここで A と B は N に含まれ、a は Σ に含まれる。
- A → ε - ここで A は N に含まれる。
右正規文法 G の例を示す。G は、N = {S, A}, Σ = {a, b, c} から構成され、Pには以下の規則がある。
- S → aS
- S → bA
- A → ε
- A → cA
S は開始記号である。この文法を等価な正規表現で表すと a*bc* となる。
正規文法（せいきぶんぽう、Regular Grammar）には、これら右正規文法と左正規文法がある。
正規文法は全ての正規言語を記述することができ、そういう意味では有限オートマトンや正規表現と等価である。さらに言えば、右正規文法も左正規文法も同じ正規言語を定義することができる。
正規文法は全て文脈自由文法に含まれる。
全ての文脈自由文法は、左正規規則と右正規規則の組み合わせに容易に変換可能である。つまり、右正規文法と左正規文法を合成することで全ての文脈自由言語を表現可能である。正規文法は左正規規則か右正規規則を使用するが、同時に両者を使用することはない。そのため、より狭い範囲の言語である正規言語だけを記述できる。
正規文法に空記号（ε）を許さない場合もある。
