About: Equivalence (formal languages)

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Equivalence (formal languages) Goto Sponge NotDistinct Permalink

An Entity of Type : yago:WikicatFormalLanguages, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon

http://dbpedia.demo.openlinksw.com/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FEquivalence_%28formal_languages%29&invfp=IFP_OFF&sas=SAME_AS_OFF

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.

Attributes	Values
rdf:type	yago:Abstraction100002137 yago:Communication100033020 yago:Language106282651 yago:WikicatFormalLanguages
rdfs:label	Equivalence (formal languages) (en)
rdfs:comment	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. (en)
foaf:depiction
dcterms:subject	Formal languages
Wikipage page ID	34615237 (xsd:integer)
Wikipage revision ID	1069577574 (xsd:integer)
Link from a Wikipage to another Wikipage	Indexed grammar Context-free grammar Generative grammar Order of operations Combinatory categorial grammar Compiler theory Concrete syntax tree Tree-adjoining grammar Backus-Naur form Head-driven phrase structure grammar Head grammar Noam Chomsky Formal language Formal languages Parse tree Postfix traversal Formal grammars
sameAs	Equivalence (formal languages) Equivalence (formal languages) Equivalence (formal languages) Equivalence (formal languages) Equivalence (formal languages)
dbp:wikiPageUsesTemplate	dbt:Clarify dbt:Reflist dbt:Short_description dbt:Use_American_English
thumbnail	wiki-commons:Special:FilePath/Parse_Tree_Derivations_ETF.svg?width=300
date	February 2014 (en)
reason	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. (en) 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. (en)
has abstract	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. (en)
prov:wasDerivedFrom	wikipedia-en:Equivalence_(formal_languages)?oldid=1069577574&ns=0
page length (characters) of wiki page	7437 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:Equivalence_(formal_languages)
is Link from a Wikipage to another Wikipage of	Indexed grammar Indexed language Weak generative capacity Generalized context-free grammar Equivalence Chomsky normal form Strong generative capacity Weak equivalence (formal languages)
is Wikipage redirect of	Weak generative capacity Strong generative capacity Weak equivalence (formal languages)
is Wikipage disambiguates of	Equivalence
is foaf:primaryTopic of	wikipedia-en:Equivalence_(formal_languages)

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 51 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software