Talk:Chomsky–Schützenberger theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Another theorem with the same name[edit]

There is a well-known theorem also called "Chomsky-Schützenberger theorem", here it is for example: http://planetmath.org/encyclopedia/ChomskySchutzenbergerTheorem.html I think this article should explain both. — Preceding unsigned comment added by 201.231.234.10 (talk) 06:45, 8 September 2011 (UTC)

Meanwhile, the article explains both theorems. Hermel (talk) 12:39, 18 July 2014 (UTC)

Usage[edit]

A simple example showing the theorem's use would be helpful. Virgil H. Soule (talk) 15:13, 17 July 2014 (UTC)

I have added an example explaining how the theorem about counting words can be used to prove that certain context-free languages do not admit an unambiguous grammar. The theorem can be of course used in many ways, so more examples are welcome. Hermel (talk) 12:39, 18 July 2014 (UTC)
I have added another example explaining how the theorem about counting words can be used for asymptotic estimates. Hermel (talk) 20:55, 31 July 2014 (UTC)