Balanced-by-Construction regular and ω-Regular languages

Parenn is the typical generalization of the Dyck language to multiple types of parentheses. We generalize its notion of balancedness to allow parentheses of different types to freely commute. We show that balanced regular and ω-regular languages can be characterized by syntactic constraints on regular and ω-regular expressions and, using the shuffle on trajectories operator, we define grammars for balanced-by-construction expressions with which one can express every balanced regular and ω-regular language.

• View at Publisher

Full Text ( Author Manuscript , 476kb )

See Also
inProceedings Balanced-by-construction regular and ω -regular languages L.J. Edixhoven (Luc) and S.-S.T.Q. Jongmans (Sung)