形式文法

形式文法 G は 集合 N, Σ, P と状態 S を用いて表される。

G = <N, Σ, P, S>

  • N: non-terminal symbol, 非終端記号
  • Σ: terminal symbol, 終端記号
  • P: rewriting rule, 書き換え規則
  • S: initial Symbol, 初期記号 (S is in N)

書き換え規則 p : α -> β について、 p, α, β をそれぞれ書き換え規則の名前、左辺、右辺という。

  • 非終端規則 (non-terminating rule): 右辺に非終端記号を含む
  • 終端規則 (terminating rule): 右辺に非終端記号を含まない
  • 空語規則 (ε-rule): 右辺が ε

左辺から右辺が導出されることを “=>” で表す。

文法 G によって導出される言語 L(G) は次の様に表される。

L(G) = { w S =>* w in Σ* }

(ここで * は 0回以上の繰り返しを表している。)

文法の分類(クラス)

上の 文法 G において、 空語規則を持たない場合、 次の様に言語を分類できる。 V = N + Σ, V+ = V* - { ε } とする。

  • 文脈依存文法
    • すべての書き換え規則 α -> β について、 α = α1Aα2, β = α1γα2 の形をしている。 (A in N, α1, α2 in V*, γ in V+)
  • 文脈自由文法
    • すべての書き換え規則について α = A。 (A in N, β in V+)
    • 空語規則を持たないので β in V+。 通常の定義では β in V*。
  • 正規文法
    • すべての書き換え規則について α in A, β = aB or a。 (A, B in N, a in Σ)

空語を含む言語についての書き換え規則は S -> ε のみがあれば十分である。 (左辺が S でない書き換え規則は a -> b のように異なる記号を当てはめて整理することで、 空語規則を S -> ε のみにすることができる。) G から唯一の空語規則 S -> ε を除いて得られる文法を G’ とするとき、 G と G’ は同じクラスの文法であるとする。

正規表現

正規表現は、次の様に和集合演算、連接演算、スター閉包を用いて再帰的に定義できる。 Σ をアルファベットとする。

  • ∅(空集合), ε(空語) は正規表現。
  • 任意の a &in; Σ について、 a は正規表現。
  • 正規表現 r1, r2 について、 (r1 + r2), r1r2, r1* も正規表現。

ここで εr = rε = r, r∅ = ∅r = ∅。