Cybernetics And Systems Analysis
International Theoretical Science
Journal
|
1 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine |
Abstract. A method is proposed for constructing the – ω -regular expression that defines the intersection of sets of – ω -words represented by – ω -regular expressions R1 and R2. Such constructing is carried out without passing to ω -automata, that is by direct transformation of the expression R = R1⋂ R2. The process of constructing – ω -regular expression defining the intersection R1⋂ R2 is represented in the form of an intersection tree whose vertices correspond to intersections of simple – ω -regular expressions obtained during the transformation of the intersection R1⋂ R2. The tree constructed in this way defines a system of linear equations with variables whose values are sets of – ω -words. One of these variables R corresponds to the set of – ω -words defined by R1⋂ R2. The – ω -regular expression defining the intersection R1⋂ R2 is the value of the variable R in the solution for this linear equation system.
Keywords: left-infinite word (– ω -word), – ω -regular expression, simple – ω -regular expression, – ω -expansion, *-expansion, intersection tree.
