Equivalence (formal languages)

In compiler theory the notion is distinguished from strong (or structural) equivalence, which additionally means that the two parse trees[clarification needed] are reasonably similar in that the same semantic interpretation can be assigned to both.

Kornai and Pullum (1990)[4] and Miller (1994)[5] 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)[6] offers a proof that for any LTAG formalism, there is a strongly equivalent HPSG one.

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 ")".

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.