Representation theorems on regular languages

摘要

Let T denote the set of regular operators, concatenation (·), union (∪), and star(∗). For any subset Ω of T, any regular language R, and any finite class C of relgular languages, R is said to have a Ω-representation over C if R can be obtained by a finite number of applications of operators in Ω to C This paper shows that there exist algorithms for deciding whether or not an arbitrary regular language has a Ω-representation over an arbitrary class C of regular languages for any subset Ω of T.