等価性（形式言語）

形式言語理論では、 2 つの文法の弱い等価性とは、それらが同じ文字列の集合を生成すること、つまりそれらが生成する形式言語が同じであることを意味します。コンパイラ理論では、この概念は強い（または構造的な）等価性とは区別されます。強い等価性とは、さらに、2 つの構文解析木が合理的に類似しており、両方に同じ意味解釈を割り当てることができることを意味します。^{[ 1 ]}

Vijay-ShankerとWeir（1994）^{[ 2 ]}は、線形インデックス文法、組み合わせカテゴリ文法、木隣接文法、およびヘッド文法は、すべて同じ文字列言語を定義するという意味で、弱等価な形式体系であることを示しています。

一方、2 つの文法が同じ派生ツリーのセット (またはより一般的には、同じ抽象構文オブジェクトのセット) を生成する場合、2 つの文法は強く等価である。チョムスキー (1963) ^{[ 3 ]}は強い等価性の概念を導入し、文法形式を比較する際には強い等価性のみが重要であると主張した。コルナイとプルム (1990) ^{[ 4 ]}およびミラー (1994) ^{[ 5 ]}は、異なる形式によって与えられる構文解析間の同型関係を可能にする、より洗練された強い等価性の概念を提示した。吉永、宮尾、辻井 (2002) ^{[ 6 ]}は、任意のLTAG形式に対して、強く等価なHPSG形式が存在することを証明した。

例として、バッカス・ナウア記法で表された以下の2つの文脈自由文法を考えてみましょう。[^{注1 ]}

<式> ::= <式> "+" <式> | <式> "-" <式> | <式> "*" <式> | <式> "/" <式> | "x" | "y" | "z" | "1" | "2" | "3" | "(" <式> ")" 

<式> ::= <項> | <式> "+" <項> | <式> "-" <項> <項> ::= <因子> | <項> "*" <因子> | <項> "/" <因子> <因子> ::= "x" | "y" | "z" | "1" | "2" | "3" | "(" <式> ")" 

どちらの文法も同じ文字列セット、すなわち変数「x」、「y」、「z」、定数「1」、「2」、「3」、演算子「+」、「-」、「*」、「/」、括弧「(」と「)」から構築できるすべての算術式のセットを生成します。ただし、 2番目の文法の具体的な構文木は常に通常の演算順序を反映しますが、1番目の文法の木は必ずしもそうではありません。

例の文字列「1+2*3」の場合、図の右側は、2 番目の文法による一意の構文解析木を示しています。^{[注 2 ]}この木を後置順で評価すると、適切な値である 7 が得られます。一方、図の左側は、その文字列に対する最初の文法による構文解析木の 1 つを示しています。これを後置順で評価すると 9 が得られます。

2番目の文法は左側の図に対応する木構造を生成できないのに対し、1番目の文法は生成できるため、両方の文法は厳密には同等ではない。

言語学では、文法の弱い生成能力は、その文法によって生成されるすべての文字列の集合として定義され、^{[注3 ]}文法の強い生成能力は、その文法によって生成される「構造記述」の集合を指します。^{[注4 ] [ 7 ]}その結果、2 つの文法の弱い生成能力が一致する場合、それらの文法は弱く同等であるとみなされます。強い同等性についても同様です。生成能力 の概念は、1963 年にノーム・チョムスキーによって導入されました。^{[ 3 ] [ 7 ]}