Parikh's theorem (original) (raw)

About DBpedia

Parikh's theorem in theoretical computer science says that if one looks only at the number of occurrences of each terminal symbol in a context-free language, without regard to their order, then the language is indistinguishable from a regular language. It is useful for deciding that strings with a given number of terminals are not accepted by a context-free grammar. It was first proved by Rohit Parikh in 1961 and republished in 1966.

Property Value
dbo:abstract Parikh's theorem in theoretical computer science says that if one looks only at the number of occurrences of each terminal symbol in a context-free language, without regard to their order, then the language is indistinguishable from a regular language. It is useful for deciding that strings with a given number of terminals are not accepted by a context-free grammar. It was first proved by Rohit Parikh in 1961 and republished in 1966. (en) En informatique théorique, et notamment dans la théorie des langages algébriques, le théorème de Parikh est un théorème qui compare les fréquences relatives d'apparition des lettres dans un langage algébrique. Il dit que si on compte, dans un langage formel, uniquement le nombre d'apparitions des lettres dans un mot, on ne peut pas distinguer les langages algébriques des langages rationnels. Ce théorème a été prouvé par Rohit Parikh en 1966, et il figure dans bon nombre de manuels d'informatique théorique. (fr) 在理論計算機科學中,帕里克定理指出,对于上下文无关语言,如果只关心其中每个终止符号出现的次数,而不考虑它们的顺序,那么存在正则语言与其对应。这个定理可用于确定具有给定数量终止符号的字符串是否能为上下文无关语法接受。1961年第一次证明了它,论文于1966年再次发表。 (zh)
dbo:wikiPageID 26511174 (xsd:integer)
dbo:wikiPageLength 4943 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1059756872 (xsd:integer)
dbo:wikiPageWikiLink dbr:Rohit_Jivanlal_Parikh dbr:Context-free_grammar dbr:Context-free_language dbr:Theoretical_computer_science dbr:Alphabet_(formal_languages) dbr:Ambiguous_grammar dbr:Formal_grammar dbr:Regular_language dbc:Formal_languages dbr:Inherently_ambiguous_language
dbp:date April 2017 (en)
dbp:reason why exactly? (en)
dbp:wikiPageUsesTemplate dbt:Explain
dct:subject dbc:Formal_languages
rdf:type yago:Abstraction100002137 yago:Communication100033020 yago:Language106282651 yago:WikicatFormalLanguages
rdfs:comment Parikh's theorem in theoretical computer science says that if one looks only at the number of occurrences of each terminal symbol in a context-free language, without regard to their order, then the language is indistinguishable from a regular language. It is useful for deciding that strings with a given number of terminals are not accepted by a context-free grammar. It was first proved by Rohit Parikh in 1961 and republished in 1966. (en) En informatique théorique, et notamment dans la théorie des langages algébriques, le théorème de Parikh est un théorème qui compare les fréquences relatives d'apparition des lettres dans un langage algébrique. Il dit que si on compte, dans un langage formel, uniquement le nombre d'apparitions des lettres dans un mot, on ne peut pas distinguer les langages algébriques des langages rationnels. Ce théorème a été prouvé par Rohit Parikh en 1966, et il figure dans bon nombre de manuels d'informatique théorique. (fr) 在理論計算機科學中,帕里克定理指出,对于上下文无关语言,如果只关心其中每个终止符号出现的次数,而不考虑它们的顺序,那么存在正则语言与其对应。这个定理可用于确定具有给定数量终止符号的字符串是否能为上下文无关语法接受。1961年第一次证明了它,论文于1966年再次发表。 (zh)
rdfs:label Théorème de Parikh (fr) Parikh's theorem (en) 帕里克定理 (zh)
owl:sameAs freebase:Parikh's theorem yago-res:Parikh's theorem wikidata:Parikh's theorem dbpedia-fa:Parikh's theorem dbpedia-fr:Parikh's theorem dbpedia-zh:Parikh's theorem https://global.dbpedia.org/id/4tKXC
prov:wasDerivedFrom wikipedia-en:Parikh's_theorem?oldid=1059756872&ns=0
foaf:isPrimaryTopicOf wikipedia-en:Parikh's_theorem
is dbo:knownFor of dbr:Rohit_Jivanlal_Parikh
is dbo:wikiPageWikiLink of dbr:Rohit_Jivanlal_Parikh dbr:Context-free_language dbr:Ambiguous_grammar
is foaf:primaryTopic of wikipedia-en:Parikh's_theorem