正規表現と文脈自由文法の主な違いは、正規表現が正規言語のすべての文字列を記述するのに役立つのに対し、文脈自由文法は文脈自由言語のすべての可能な文字列を定義するのに役立つという点です。
文法とは、自然言語における会話のための構文規則を意味する。
コンピュータサイエンスは、形式言語の理論を大いに利用している。
1956年、ノーム・チョムスキーはコンピュータ言語を記述するための文法の数学的モデルを示した。
ある文法からすべての文字列の集合を導き出すことができるとき、その文法から言語が生成されたという。
文法には、正則文法と文脈自由文法の2種類があります。
正規表現で記述できる言語はすべて正規言語です。
文脈自由文法は正規表現を一般化したものです。
正規表現を用いて正規言語を記述し、文脈自由文法を用いて文脈自由文法を記述することができる。
正規表現とは
正規文法は、正規の言語を生成する。
この文法は、左辺に単一の非終端を持ち、右辺は単一の終端または単一の終端に続く単一の非終端からなる。
次のような生成規則を持つことができる。
X -> a または X -> a Y
ここで、X, Y ϵ N (非終端記号) と a ϵ T (終端記号)です。
正規表現は、正規言語を記述するための正規文法を書くのに役立つ。
- 終端記号、ヌル記号、空記号は正規表現です。
-
- 2つの正規表現の和は正規表現です。
-
- 2つの正規表現の連結は正規表現です。
-
- 繰り返しや閉包は正規表現です。
集合{0,1,2}に対する正規表現は次の通りです。
R = 0 + 1+2
集合{abb,a,b,bba}は以下の正規表現で表すことができる。
R = abb + a +b + bba
集合、{ϵ, 0, 00, 000, …}を考える。
ϵは空文字列です。
正規表現は、R = 0.0* となる。
これは空文字を含む記号の閉包を表す。
集合{1, 11, 111, 1111, ….}において
正規表現はR = 1 +.This +は空白の記号を除いた記号の閉包を表す。
文脈自由文法とは
形式言語理論において、文脈自由言語(Context Free Language, CFL)は文脈自由文法によって生成される言語です。
文脈自由文法(G)は4つのパラメータで定義される。
g= {v, ∑ , s, p} とする。
V: 可変記号または非終端記号の集合。
∑: 終端記号の集合
S: 開始シンボル
P: 生成規則
文脈自由文法は、以下のような生成規則を持つ。
A -> a ここで a = {V, ∑ }* and A ϵ V
文脈自由文法の一例は以下の通りです。
各生成規則は、非終端記号と正規表現からなる。
aとbを同数生成する言語の生成には、anbnという形式があります。
文脈自由文法は以下の通りです。
G = {(S,A), (a,b), (S ->aAb, A -> aAb | ϵ ) } とする。
開始記号を考える。
S – > a A b
A -> aAb を適用することで
→ a a a b b
再びA→aAbを適用することで
→ a a a a a b b b
A -> ϵ (この記号は空文字列を表す)を適用することで
→ a a a b b b
→ a 3 b 3
出力を考えると、aの数はbの数と等しい。
これは an bn 形式です。
正規表現と文脈自由文法の関係
- 文脈自由文法は正規表現を一般化したものです。
正規表現と文脈自由文法の違い
定義
正規表現とは、形式言語理論における概念で、検索パターンを定義する文字列のことである。
文脈自由文法は、形式言語理論における形式文法の一種で、与えられた形式言語において可能なすべての文字列を記述する生成規則の集合である。
使用方法
正規表現は、ある文字列の集合を代数的に表現するのに役立ちます。
正規表現を使うことで、正規言語を表現することができる。
文脈自由文法は、文脈自由言語のすべての可能な文字列を定義するのに役立つ。
結論
正規表現とは、パターンマッチの手法の一つです。
文字列のマッチングを行うための柔軟で簡潔な手段を提供するものです。
正規表現に属するすべての文字列を定義する。
一方、文脈自由文法は、文脈自由言語に属するすべての文字列を定義することができる。
正規表現と文脈自由文法の違いは、正規表現が正規言語のすべての文字列を記述するのに役立つのに対し、文脈自由文法は文脈自由言語のすべての可能な文字列を定義するのに役立つ点である。
