УДК 519.713.1
А.М. ЧЕБОТАРЬОВ,
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна,
ancheb@gmail.com
ПЕРЕТИН – ω -РЕГУЛЯРНИХ ВИРАЗІВ
Анотація. Запропоновано метод побудови – ω -регулярного виразу,
що задає перетин мно-жин – ω -слів,
поданих у вигляді – ω -регулярних виразів R1 і R2.
Така побудова здійсню-ється без переходу до ω -автоматів,
тобто безпосереднім перетворенням виразу R = R1⋂ R2.
Процес побудови – ω -регулярного виразу, що задає перетин R1⋂ R2,
подано у вигляді дерева перетинів, вершини якого відповідають перетинам простих – ω -регуляр-них виразів,
отриманих під час перетворення перетину R1⋂ R2.
Побудоване дерево пере-тинів визначає систему лінійних рівнянь
зі змінними, значеннями яких є множини – ω -слів.
Одна з цих змінних R відповідає множині – ω -слів,
що задається перетином R1⋂ R2,
тобто вираз, який задає перетин – ω -регулярних виразів R1 і R2,
є значенням змінної R у розв’язку цієї системи лінійних рівнянь.
Ключові слова: зворотне надслово, – ω -регулярний вираз,
простий – ω -регулярний вираз,
– ω -розгортка, *-розгортка, дерево перетинів.
ПОВНИЙ ТЕКСТ
СПИСОК ЛІТЕРАТУРИ
- Thiemann P., Sulzmann M. From ω -regular expressions to Buchi automata via partial derivatives. Lecture Notes Comput. Sci. Berlin; Heidelberg: Springer-Verlag, 2015. Vol. 8977. P. 287–298.
- Loding C., Tollkotter A. Transformations between regular expressions and ω -automata. Proc. 41th Int. Symp. on Mathematical Foundation of Computer Science (MFCS 2016, Aug 22–26, Krakow, Poland). Aachen, Germany: Dagstuhl Publishing, 2016. P. 88:1–88:13.
- Mukund M. Finite state automata on infinite inputs. Modern Application of Automata Theory. D’Souza D., Shankar P. (eds.). Singapore: World Scientific Press, 2012. P. 45–78.
- Thomas W. Automata on infinite objects. Handbook of Theoretical Comput. Science. Leeuwen J. van (ed.). Amsterdam: Elsevier Science Publishers, 1990. P. 134–191.
- Чеботарев А.Н. Синтез ∑-автоматов, специфицированных в логических языках LP и LF первого порядка. Кибернетика и системный анализ. 2018. Т. 54, № 4. С. 16–31.
- Чеботарев А.Н. Определение фиктивных состояний в автомате, синтезированном по спецификации в языке LP. Кибернетика и системный анализ. 2019. Т. 55, № 5. С. 47–57.
- Staiger L. On ω -power languages. New Trends in Formal Languages. LNCS. Berlin; Heidelberg: Springer-Verlag, 1997. Vol. 1218. P. 377–394.
