正規文法

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

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

  1. A → a
  2. A → aB
  3. A → ε

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

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

  1. A → a
  2. A → Ba
  3. A → ε

例

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

S → aS
S → bA
A → ε
A → cA

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

概要

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

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

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

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

関連項目