formal language In logic, mathematics, computer science, and linguistics, a formal language is a set of strings whose symbols are taken from a set called "alphabet". The alphabet of a formal language consists of symbols that concatenate into strings (also c ...

theory, weak equivalence of two

grammar In linguistics, grammar is the set of rules for how a natural language is structured, as demonstrated by its speakers or writers. Grammar rules may concern the use of clauses, phrases, and words. The term may also refer to the study of such rul ...

s means they generate the same set of strings, i.e. that the formal language they generate is the same. In

compiler theory In computing, a compiler is a computer program that Translator (computing), translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primaril ...

the notion is distinguished from strong (or structural) equivalence, which additionally means that the two

parse tree A parse tree or parsing tree (also known as a derivation tree or concrete syntax tree) is an ordered, rooted tree that represents the syntactic structure of a string according to some context-free grammar. The term ''parse tree'' itself is use ...

s are reasonably similar in that the same semantic interpretation can be assigned to both. Vijay-Shanker and Weir (1994) demonstrates that

Linear Indexed Grammars In mathematics, the term ''linear'' is used in two distinct senses for two different properties: * linearity of a ''function'' (or '' mapping''); * linearity of a ''polynomial''. An example of a linear function is the function defined by f(x)=( ...

, 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)Kornai, A. and Pullum, G. K. 1990. ''The X-bar Theory of Phrase Structure''. Language, 66:24-50. and Miller (1994)Miller, Philip H. 1999. ''Strong Generative Capacity''. CSLI publications. 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 Head-driven phrase structure grammar (HPSG) is a highly lexicalized, constraint-based grammar developed by Carl Pollard and Ivan Sag. It is a type of phrase structure grammar, as opposed to a dependency grammar, and it is the immediate successor t ...

one.

Context-free grammar example

As an example, consider the following two

context-free grammar In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules can be applied to a nonterminal symbol regardless of its context. In particular, in a context-free grammar, each production rule is of the fo ...

s,with the start symbol "" given in Backus-Naur form: ::= "+" , "-" , "*" , "/" , "x" , "y" , "z" , "1" , "2" , "3" , "(" ")" ::= , "+" , "-" ::= , "*" , "/" ::= "x" , "y" , "z" , "1" , "2" , "3" , "(" ")" 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 A parse tree or parsing tree (also known as a derivation tree or concrete syntax tree) is an ordered, rooted tree that represents the syntactic structure of a string according to some context-free grammar. The term ''parse tree'' itself is used p ...

of the second grammar always reflects the usual

order of operations In mathematics and computer programming, the order of operations is a collection of rules that reflect conventions about which operations to perform first in order to evaluate a given mathematical expression. These rules are formalized with a ...

, 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;using the abbreviation "E", "T", and "F" for , , and , respectively 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.

Generative capacity

In linguistics, the weak generative capacity of a

is defined as the set of all strings generated by it,for context-free grammars: see Context-free grammar#Context-free language for a formal definition while a grammar's strong generative capacity refers to the set of "structural descriptions"for context-free grammars:

s generated by it. As a consequence, two grammars are considered weakly equivalent if their weak generative capacities coincide; similar for strong equivalence. The notion of ''generative capacity'' was introduced by

Noam Chomsky Avram Noam Chomsky (born December 7, 1928) is an American professor and public intellectual known for his work in linguistics, political activism, and social criticism. Sometimes called "the father of modern linguistics", Chomsky is also a ...

in 1963.

Notes

References

{{DEFAULTSORT:Equivalence Formal languages