接続文法

連言文法は、形式言語理論 で研究される形式文法の一種です。連言文法は、基本的な文法の種類である文脈自由文法を連言演算で拡張します。明示的な連言の他に、連言文法では、単一の非終端記号に対して複数の規則で表される暗黙的な選言が可能です。これは、文脈自由文法で表現できる唯一の論理接続子です。特に、連言は言語の共通部分を指定するために使用できます。ブール文法 として知られる連言文法のさらなる拡張では、明示的な否定 も可能になります。

接続文法の規則は次の形式である。

${\displaystyle A\to \alpha _{1}\And \ldots \And \alpha _{m}}$

ここで、は非終端記号であり 、 、... はおよび（それぞれ終端記号と非終端記号の有限集合） 内の記号で形成された文字列です。非公式には、このような規則は、 、... によって表される各構文条件を満たす上のすべての文字列は、 したがって によって定義された条件を満たすと主張します。 ${\displaystyle A}$${\displaystyle \alpha _{1}}$${\displaystyle \alpha_{m}}$${\displaystyle \Sigma }$${\displaystyle V}$${\displaystyle w}$${\displaystyle \Sigma }$${\displaystyle \alpha _{1}}$${\displaystyle \alpha_{m}}$${\displaystyle A}$

連言文法は4つの組で定義され、 ${\displaystyle G}$ ${\displaystyle G=(V,\シグマ,R,S)}$

1. Vは有限集合です。各要素は非終端記号または変数と呼ばれます。各変数は文中の異なる種類の句または節を表します。変数は統語カテゴリと呼ばれることもあります。${\displaystyle v\in V}$
2. Σ は、Vとは独立し、文の実際の内容を構成している終端記号の有限集合です。終端記号の集合は、文法Gによって定義された言語のアルファベットです。
3. R は、および内のいくつかの に対して という形式を持つ、生成規則の有限集合です。R のメンバーは、文法の規則または生成規則と呼ばれます。${\displaystyle A\rightarrow \alpha _{1}\&\ldots \&\alpha _{m}}$${\displaystyle A}$${\displaystyle V}$${\displaystyle \alpha _{i}\in (V\cup \Sigma )^{*}}$
4. S は開始変数（または開始シンボル）であり、文全体（またはプログラム）を表すために使用されます。これはVの要素である必要があります。

同じ左辺に対するすべての右辺を、| (パイプ記号) を使用して区切って同じ行にリストするのが一般的です。したがって、および の規則はと記述できます。 ${\displaystyle A\rightarrow \alpha _{1}\&\ldots \&\alpha _{m}}$${\displaystyle A\rightarrow \beta _{1}\&\ldots \&\beta _{n}}$${\displaystyle A\rightarrow \alpha _{1}\&\ldots \&\alpha _{m}\ |\ \beta _{1}\&\ldots \&\beta _{n}}$

連言文法によって指定される言語には、同等の形式定義が 2 つ存在します。1 つの定義は、文法を和集合、積集合、連結を含む言語方程式のシステムとして表現し、その最小解を考慮することに基づいています。もう 1 つの定義は、 連言と連結に関する項の書き換えを使用して、文脈自由文法の チョムスキーの生成定義を一般化したものです。

任意の文字列 に対して、 u は直接v を生成すると言い、次のように表される。 ${\displaystyle u,v\in (V\cup \Sigma \cup \{{\text{“(”}},{\text{“}}\&{\text{”}},{\text{“)”}}\})^{*}}$${\displaystyle u\Rightarrow v\,}$

• または、となるような規則が存在するか、${\displaystyle A\rightarrow \alpha _{1}\&\ldots \&\alpha _{m}\in R}$${\displaystyle u\,=u_{1}Au_{2}}$${\displaystyle v\,=u_{1}(\alpha _{1}\&\ldots \&\alpha _{m})u_{2}}$
• または、 かつとなるような文字列が存在します。${\displaystyle w\in (V\cup \Sigma )^{*}}$${\displaystyle u\,=u_{1}(w\&\ldots \&w)u_{2}}$${\displaystyle v\,=u_{1}wu_{2}}$

任意の文字列に対して、となる場合、 G はと表記されるw を生成すると言います。 ${\displaystyle w\in \Sigma ^{*},}$ ${\displaystyle S\ {\stackrel {*}{\Rightarrow }}\ w}$${\displaystyle \exists k\geq 1\,\exists \,u_{1},\cdots ,u_{k}\in (V\cup \Sigma \cup \{{\text{“(”}},{\text{“}}\&{\text{”}},{\text{“)”}}\})^{*}}$${\displaystyle S=\,u_{1}\Rightarrow u_{2}\Rightarrow \cdots \Rightarrow u_{k}\,=w}$

文法の言語は、文法が生成するすべての文字列の集合です。 ${\displaystyle G=(V,\Sigma ,R,S)}$

文法と生成 ${\displaystyle G=(\{S,A,B,C,D\},\{a,b,c\},R,S)}$

${\displaystyle S\rightarrow AB\&DC}$、

${\displaystyle A\rightarrow aA\ |\ \epsilon }$、

${\displaystyle B\rightarrow bBc\ |\ \epsilon }$、

${\displaystyle C\rightarrow cC\ |\ \epsilon }$、

${\displaystyle D\rightarrow aDb\ |\ \epsilon }$、

は接続詞である。典型的な派生語は

${\displaystyle S\Rightarrow (AB\&DC)\Rightarrow (aAB\&DC)\Rightarrow (aB\&DC)\Rightarrow (abBc\&DC)\Rightarrow (abc\&DC)\Rightarrow (abc\&aDbC)\Rightarrow (abc\&abC)\Rightarrow (abc\&abcC)\Rightarrow (abc\&abc)\Rightarrow abc}$

であることが示せます。言語は文脈自由ではなく、文脈自由言語のポンピング補題によって証明されます。 ${\displaystyle L(G)=\{a^{n}b^{n}c^{n}:n\geq 0\}}$

連言文法の表現力は文脈自由文法よりも優れていますが、連言文法は文脈自由文法の一部を保持しています。最も重要なのは、線形時間の再帰降下、3 次時間の一般化 LR、3 次時間のCocke-Kasami-Younger、および行列乗算と同じ速度で実行されるValiantアルゴリズムなど、主要な文脈自由構文解析アルゴリズムの一般化があることです。

文脈自由言語やそれらの有限積集合に対してすでに決定不可能な性質は、連言文法に対しても決定不可能でなければならない。これには、 空性、有限性、規則性、文脈自由性、^{[n 1]}包含性、同値性などが含まれる。^{[n 2]}

連言言語族は和集合、積集合、連結集合、クリーネスター集合の下では閉じているが、文字列準同型、接頭辞、接尾辞、部分文字列の下では閉じていない。補集合の下での閉包とε-フリー文字列準同型の下での閉包は未解決問題である（2001年現在）。^{[1] : 533}

1文字のアルファベットに対する文法の表現力が研究されてきた。^[要出典]

この研究は、より一般的な形式の 言語方程式の研究の基礎を提供しました。

AizikowitzとKaminski ^[2]は、同期交互プッシュダウンオートマトン（SAPDA）と呼ばれる新しいクラスのプッシュダウンオートマトン（PDA）を導入しました。彼らは、非決定性PDAが文脈自由文法と同等であるのと同じように、SAPDAが連言文法と同等であることを証明しました。

• Artur Jeż (2007) 「接続文法は非正規単項言語を生成する」(PDF) (言語理論の発展に関する国際会議で行われた講演のスライド) 。2019年11月5日閲覧。
• 「アレクサンダー・オホーチンの接続文法に関するページ」。2011年10月9日。 2019年11月5日閲覧。
• Alexander Okhotin (2007)。「連言文法とブール文法に関する 9 つの未解決問題」。Bulletin of the EATCS。2007年 9 月 29 日のオリジナルからアーカイブ。
• Alexander Okhotin (2013)。「接続文法とブール文法: 文脈自由文法の真の一般的なケース」。Computer Science Review。9 : 27–59。doi :10.1016/j.cosrev.2013.06.001。この論文は、以前の調査「接続文法の概要」( Bulletin of the EATCS、2004) および「接続文法とブール文法に関する 9 つの未解決問題」に代わるものです。
• Jeż, Artur (2008). 「接続文法は非正規単項言語を生成する」. International Journal of Foundations of Computer Science . 19 (3​​): 597–615. doi :10.1142/S012905410800584X.技術レポートバージョン (pdf) ^{[永久リンク切れ‍ ]}