dbs@PRC.Unisys.COM (David Searls) (08/03/90)
A theorem by Chomsky and Schutzenberger established the equivalence of
ANY context-free language to a homomorphic image of the intersection
of some regular language with a semi-Dyck set. (See, for instance,
Harrison chapter 10.4). A semi-Dyck set is a language consisting of
strings of well-balanced parentheses, brackets, braces, etc. so that
the string "[()({}())]([])" is a member of the semi-Dyck set of size
three (i.e. three types of parens), whereas "[()[" is not.
Can anyone tell me what befalls this theorem if, instead of semi-Dyck
sets, the full or two-sided Dyck sets are allowed? These also allow
cancellation of like parens facing opposite, e.g. "(][)}{" is in a
two-sided Dyck set. I believe the proofs I have seen fall apart,
but I haven't seen any better characterization of what happens. I
would appreciate any references that bear on this.
David Searls, dbs@prc.unisys.com