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.
Attributes | Values |
---|
rdf:type
| |
rdfs:label
| - Théorème de Parikh (fr)
- Parikh's theorem (en)
- 帕里克定理 (zh)
|
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)
|
dcterms:subject
| |
Wikipage page ID
| |
Wikipage revision ID
| |
Link from a Wikipage to another Wikipage
| |
sameAs
| |
dbp:wikiPageUsesTemplate
| |
date
| |
reason
| |
has 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)
|
prov:wasDerivedFrom
| |
page length (characters) of wiki page
| |
foaf:isPrimaryTopicOf
| |
is Link from a Wikipage to another Wikipage
of | |
is known for
of | |
is foaf:primaryTopic
of | |