A Note on SE-Systems and Regular Canonical Systems

Article type: Research Article

Authors: Ţiplea, Ferucio Laurenţiu | Mäkinen, Erkki

Abstract: A synchronized extension system is a 4-tuple G=(V,L_1,L_2,S), where V is an alphabet and L_1, L_2 and S are languages over V. Such systems generate languages extending L_1 by L_2 to the left or to the right, and synchronizing on words in S. In this note we consider the relationship between synchronized extension systems and regular canonical systems. We are able to give a simplified and generalized proof for the classical result concerning the regularity of the languages defined by regular canonical systems.

Keywords: formal languages, synchronized extension systems, regular canonical systems

Journal: Fundamenta Informaticae, vol. 46, no. 3, pp. 253-256, 2001