Equivalence (formal languages)

rdf:langString Equivalence (formal languages)

rdf:langString February 2014

rdf:langString In the Chomsky hierarchy of grammars, parse trees can be defined only for context-free grammars . For example, the derivation of 'aaabbbccc' shown in 'Context-sensitive grammar#Examples' doesn't correspond to a tree.

rdf:langString In the previous paragraph, weak equivalence was introduced as a relation between two grammars. In the current paragraph, it is used a relation between two 'formalisms', i.e. two classes of grammars.

rdf:langString In formal language theory, weak equivalence of two grammars means they generate the same set of strings, i.e. that the formal language they generate is the same. In compiler theory the notion is distinguished from strong (or structural) equivalence, which additionally means that the two parse trees are reasonably similar in that the same semantic interpretation can be assigned to both. 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.