線形文法

コンピュータサイエンスにおいて、線形文法とは、各生成規則の 右側に最大 1 つの非終端記号を持つ文脈自由文法です。

線形言語は、何らかの線形文法によって生成される言語です。

線形文法の例としては、N = {S}、Σ = {a, b}、開始記号Sを持つP、および規則を 持つGが挙げられる。

S → aSb

S → ε

言語を生成します。 ${\displaystyle \{a^{i}b^{i}\mid i\geq 0\}}$

線形文法には、次の 2 つの特殊なタイプがあります。

• 左線形または左正規文法。すべての規則はA → αwの形式をとり、αは空または単一の非終端記号であり、wは終端記号の文字列です。
• 右線形文法または右正規文法では、すべての規則はA → wαの形式をとります。ここで、w は終端記号の文字列であり、αは空または単一の非終端記号です。

これらはそれぞれ、正規言語を正確に記述できます。正規文法は、左線形または右線形の文法です。

新しい非終端記号を挿入することで、任意の線形文法を、一部の規則が左線形で一部が右線形である同等の文法に置き換えることができることに注意してください。たとえば、上記のGの規則は次のように置き換えることができます 。

S → aA

A → Sb

S → ε

ただし、すべての規則が左線形である (またはすべての規則が右線形である) という要件は、線形文法の表現力の大幅な低下につながります。

すべての正規言語は線形です。逆に、線形で非正規な言語の例は、上で説明したように { a ⁿ b ⁿ } です。すべての線形言語は文脈自由です。逆に、文脈自由で非線形な言語の例は、バランスの取れた括弧のペアのDyck 言語です。したがって、正規言語は線形言語の適切なサブセットであり、線形言語は文脈自由言語の適切なサブセットです。

正規言語は決定論的であるが、非決定論的な線形言語も存在する。例えば、0 と 1 のアルファベットの偶数長回文の言語は、線形文法 S → 0S0 | 1S1 | ε を持つ。この言語の任意の文字列は、最初にすべての文字を読み取らなければ解析できないため、プッシュダウンオートマトンでは、半解析文字列のさまざまな長さに対応するために、代替状態遷移を試す必要がある。^[1]この言語は非決定論的である。非決定論的な文脈自由言語は線形時間で受け入れられないため^{[明確化が必要]}、線形言語は一般に線形時間で受け入れられない。さらに、与えられた文脈自由言語が線形文脈自由言語であるかどうかは決定不能である。^[2]

言語が線形であるとは、1 ターンのプッシュダウン オートマトン (一度ポップし始めると二度とプッシュしないプッシュダウン オートマトン) によって生成できる場合に限られます。

線型言語は和集合に関して閉じています。 の構築は、文脈自由言語の和集合 の構築と同じです。 を2 つの線型言語とすると、 は を持つ線型文法によって構築され、の線型文法の役割を果たします。 ${\displaystyle L_{1},L_{2}}$${\displaystyle L_{1}\cup L_{2}}$${\displaystyle S\to S_{1}|S_{2}}$${\displaystyle S_{1},S_{2}}$${\displaystyle L_{1},L_{2}}$

Lが線形言語でM が正規言語である場合、交差も 再び線形言語になります。言い換えると、線形言語は正規集合との交差に対して閉じています。 ${\displaystyle L\cap M}$

線形言語は準同型性と逆準同型性に対して閉じている。^[3]

当然の帰結として、線形言語は完全なトリオを形成します。一般に、完全なトリオは、他のいくつかの望ましい数学的特性を備えた言語ファミリです。

線形言語は交差に関して閉じていません。たとえば、 とすると、それらの交差は線形ではないだけでなく、文脈自由でもありません。文脈自由言語についてはポンピング補題を参照してください。 ${\displaystyle L_{1}=\{a^{n}b^{n}c^{m}\mid n,m\geq 0\},L_{2}=\{a^{n}b^{m}c^{m}\mid n,m\geq 0\}}$

結果として、線形言語は補集合に対して閉じていません (ド・モルガンの法則によって和集合と補集合から交差を構築できるため)。