Loading article…
理論計算機科学と形式言語理論において、正規文法とは右正規文法または左正規文法のことである。その正確な定義は教科書によって異なるが、いずれも以下の条件を満たす必要がある。
すべての正規文法は正規言語を記述する。
右正規文法（右線形文法とも呼ばれる）は、形式文法（N、Σ、P、S ）であり、 Pのすべての生成規則は、以下のいずれかの形式である。
ここで、 A、B、S ∈ Nは非終端記号、a ∈ Σ は終端記号、ε は空文字列、すなわち長さ 0 の文字列を表します。Sは開始記号と呼ばれます。
左正規文法（左線形文法とも呼ばれる）では 、すべての規則が次の形式に従う。
ある文法によって記述される言語とは、終端記号のみを含み、開始記号から生成規則を繰り返し適用することによって導出できるすべての文字列の集合である。2つの文法が同じ言語を記述する場合、それらは弱等価であると呼ばれる。
両方の種類の規則を混同してはならない。例えば、規則セット { S → aT、T → Sb、 S→ε } を持つ文法は正規文法ではなく、言語を記述する。これもまた、規則的なものではない。
一部の教科書や論文では、空の生成規則を認めず、言語に空文字列が存在しないことを前提としている。
拡張右正規文法とは、すべての規則が以下のいずれかに従う文法である。
この種の文法を右正規文法（または右線形文法）[ 1 ]と呼び、上記のタイプを厳密右正規文法（または厳密右線形文法）[ 2 ]と呼ぶ著者もいる。
拡張左正規文法とは、すべての規則が以下のいずれかに従う文法である。
N = {S, A}、Σ = {a, b, c}、Pを持つ右正則文法Gの例は、以下の規則から構成される。
S は開始記号です。この文法は、正規表現a*bc*と同じ言語、つまり、任意の数の「 a」、1 つの「b」、そして任意の数の「c 」からなるすべての文字列の集合を記述します。
同じ正規表現に対する、やや長いが明示的な拡張右正規文法Gは、 N = {S, A, B, C}、Σ = {a, b, c}で与えられ、Pは次の規則から構成される。
...ここで、各大文字は正規表現の次の位置から始まるフレーズに対応します。
プログラミング言語の分野からの例として、浮動小数点数を表すすべての文字列の集合は、N = {S,A,B,C,D,E,F}、Σ = {0,1,2,3,4,5,6,7,8,9,+,−,.,e}の拡張右正規文法Gで記述できます。ここで S は開始記号であり、P は次の規則で構成されます。
（厳密に）右正則文法の規則と非決定性有限オートマトン規則の間には直接的な一対一対応があり、文法はオートマトンが受理する言語を正確に生成します。[ 3 ]したがって、右正則文法はすべての正則言語を正確に生成します。左正則文法は、そのようなすべての言語の逆、つまり正則言語も正確に記述します。
厳密な右正規文法はすべて拡張右正規文法であり、拡張右正規文法はすべて新しい非終端記号を挿入することで厳密化でき、その結果として同じ言語が生成される。したがって、拡張右正規文法も正規言語を生成する。同様に、拡張左正規文法も正規言語を生成する。
空の生成規則が許可されていない場合、空文字列を含まない正規言語のみが生成できます。[ 4 ]
正規文法は正規言語しか記述できないが、その逆は真ではない。正規言語は非正規文法によっても記述できる。
左正規規則と右正規規則の混在が許容される場合、線形文法は存在するが、必ずしも正規文法とは限らない。さらに、このような文法は正規言語を生成する必要もない。すべての線形文法は容易にこの形式に変換できるため、非正規言語を含むすべての線形言語を生成できることになる。
例えば、N = {S, A}、Σ = {a, b}、開始記号Sと規則を持つPを持つ文法G
生成する、典型的な非正規線形言語。
