Email Gateway (Jun 19 2025 at 10:55): Email Gateway (Jun 19 2025 at 10:55):From: Dmitriy Traytel <cl-isabelle-users@lists.cam.ac.uk>
Dear all,
Two new entries further explore properties of context-free languages. Careful: The abstract of the first one may create an unresolved tension (https://xkcd.com/859/) even if the mismatch does make sense in this context:
Dyck Language
by Tobias Nipkow and Moritz Roos
The Dyck language over a pair of brackets, e.g. ( and ), is the set of balanced strings/words/lists of brackets. That is, the set of words with the same number of ( and ), where every prefix of the word contains no more ) than (. In general, a Dyck language is defined over a whole set of matching pairs of brackets.
https://www.isa-afp.org/entries/Dyck_Language.html
Chomsky-Schützenberger Representation Theorem
by Moritz Roos
The Chomksy-Schützenberger Representation Theorem says that any context-free language is the homomorphic image of the intersection of a regular language and a Dyck language.
https://www.isa-afp.org/entries/Chomsky_Schuetzenberger.html
2 x Enjoy!
Last updated: Jun 20 2025 at 16:26 UTC