Parikh's theorem (original) (raw)
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 |