Chomsky–Schützenberger theorem
In formal language theory, the Chomsky–Schützenberger theorem may refer to either of two different theorems derived by Noam Chomsky and Marcel-Paul Schützenberger concerning context-free languages:
- The Chomsky–Schützenberger enumeration theorem about the number of words of a given length generated by an unambiguous context-free grammar
- The Chomsky–Schützenberger representation theorem representing any context-free language by a combination of a regular language and a Dyck language
This article is issued from Wikipedia - version of the 12/12/2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.