Balanced-by-construction regular and ω -regular languages
Presented at the International Conference on Developments in Language Theory (August 2021), Porto, Portugal
Parenn is the typical generalisation of the Dyck language to multiple types of parentheses. We generalise its notion of balancedness to allow parentheses of different types to freely commute. We show that balanced regular and ω -regular languages can be characterised 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.
|Lecture Notes in Computer Science|
|International Conference on Developments in Language Theory|
|Organisation||Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands|
Edixhoven, L.J, & Jongmans, S.-S.T.Q. (2021). Balanced-by-construction regular and ω -regular languages. In Developments in language theory (pp. 130–142). doi:10.1007/978-3-030-81508-0_11