Parikh's theorem
id:
parikh-s-theorem-188-6635619
title:
Parikh's theorem
text:
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.
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/Parikh%27s_theorem
date created:
2010-03-11T05:57:24Z
date modified:
2024-09-08T22:57:45Z
main entity:
{"identifier":"Q7137090","url":"https://www.wikidata.org/entity/Q7137090"}
image:
fields total:
13
integrity:
14