Equivalence (formal languages)

Vijay-Shanker and Weir (1994) demonstrates that Linear Indexed Grammars, Combinatory Categorial Grammars, Tree-adjoining Grammars, and Head Grammars are weakly equivalent formalisms, in that they all define the same string languages.

On the other hand, if two grammars generate the same set of derivation trees (or more generally, the same set of abstract syntactic objects), then the two grammars are strongly equivalent. Chomsky (1963) introduces the notion of strong equivalence, and argues that only strong equivalence is relevant when comparing grammar formalisms. Kornai and Pullum (1990) and Miller (1994) offer a refined notion of strong equivalence that allows for isomorphic relationships between the syntactic analyses given by different formalisms. Yoshinaga, Miyao, and Tsujii (2002) offers a proof that for any LTAG formalism, there is a strongly equivalent HPSG one.

Context-free grammar example

As an example, consider the following two context-free grammars, given in Backus-Naur form:

<span id="mwNg"></span><span class="p" id="mwNw"><</span><span class="nc" id="mwOA">expression</span><span class="p" id="mwOQ">></span> <span class="o" id="mwOg">::=</span> <span class="p" id="mwOw"><</span><span class="nc" id="mwPA">expression</span><span class="p" id="mwPQ">></span> "+" <span class="p" id="mwPg"><</span><span class="nc" id="mwPw">expression</span><span class="p" id="mwQA">></span> | <span class="p" id="mwQQ"><</span><span class="nc" id="mwQg">expression</span><span class="p" id="mwQw">></span> "-" <span class="p" id="mwRA"><</span><span class="nc" id="mwRQ">expression</span><span class="p" id="mwRg">></span> | <span class="p" id="mwRw"><</span><span class="nc" id="mwSA">expression</span><span class="p" id="mwSQ">></span> "*" <span class="p" id="mwSg"><</span><span class="nc" id="mwSw">expression</span><span class="p" id="mwTA">></span> | <span class="p" id="mwTQ"><</span><span class="nc" id="mwTg">expression</span><span class="p" id="mwTw">></span> "/" <span class="p" id="mwUA"><</span><span class="nc" id="mwUQ">expression</span><span class="p" id="mwUg">></span> | "x" | "y" | "z" | "1" | "2" | "3" | "(" <span class="p" id="mwUw"><</span><span class="nc" id="mwVA">expression</span><span class="p" id="mwVQ">></span> ")"

<span id="mwWA"></span><span class="p" id="mwWQ"><</span><span class="nc" id="mwWg">expression</span><span class="p" id="mwWw">></span> <span class="o" id="mwXA">::=</span> <span class="p" id="mwXQ"><</span><span class="nc" id="mwXg">term</span><span class="p" id="mwXw">></span> | <span class="p" id="mwYA"><</span><span class="nc" id="mwYQ">expression</span><span class="p" id="mwYg">></span> "+" <span class="p" id="mwYw"><</span><span class="nc" id="mwZA">term</span><span class="p" id="mwZQ">></span> | <span class="p" id="mwZg"><</span><span class="nc" id="mwZw">expression</span><span class="p" id="mwaA">></span> "-" <span class="p" id="mwaQ"><</span><span class="nc" id="mwag">term</span><span class="p" id="mwaw">></span> <span class="p" id="mwbA"><</span><span class="nc" id="mwbQ">term</span><span class="p" id="mwbg">></span> <span class="o" id="mwbw">::=</span> <span class="p" id="mwcA"><</span><span class="nc" id="mwcQ">factor</span><span class="p" id="mwcg">></span> | <span class="p" id="mwcw"><</span><span class="nc" id="mwdA">term</span><span class="p" id="mwdQ">></span> "*" <span class="p" id="mwdg"><</span><span class="nc" id="mwdw">factor</span><span class="p" id="mweA">></span> | <span class="p" id="mweQ"><</span><span class="nc" id="mweg">term</span><span class="p" id="mwew">></span> "/" <span class="p" id="mwfA"><</span><span class="nc" id="mwfQ">factor</span><span class="p" id="mwfg">></span> <span class="p" id="mwfw"><</span><span class="nc" id="mwgA">factor</span><span class="p" id="mwgQ">></span> <span class="o" id="mwgg">::=</span> "x" | "y" | "z" | "1" | "2" | "3" | "(" <span class="p" id="mwgw"><</span><span class="nc" id="mwhA">expression</span><span class="p" id="mwhQ">></span> ")"

Both grammars generate the same set of strings, viz. the set of all arithmetical expressions that can be built from the variables "x", "y", "z", the constants "1", "2", "3", the operators "+", "-", "*", "/", and parentheses "(" and ")". However, a concrete syntax tree of the second grammar always reflects the usual order of operations, while a tree from the first grammar need not.

For the example string "1+2*3", the right part of the picture shows its unique parse tree with the second grammar; evaluating this tree in postfix order will yield the proper value, 7. In contrast, the left picture part shows one of the parse trees for that string with the first grammar; evaluating it in postfix order will yield 9.

Since the second grammar cannot generate a tree corresponding to the left picture part, while the first grammar can, both grammars are not strongly equivalent.