Формальные языки и автоматы V: пары полукольцо-полумодуль Конвея и конечные автоматы
- DOI
- 10.5922/2223-2095-2009-10-1
- Страницы / Pages
- 6-41
Аннотация
Это пятая статья в серии, дающей обзор некоторых разделов теории формальных языков и автоматов с использованием полуколец, формальных степенных рядов, матриц и теории неподвижных точек. Рассмотрены основные результаты теории конечных автоматов над квемикольцами, обобщающих классические конечные автоматы, принимающие конечные и бесконечные слова, базирующиеся на парах полукольцо - полумодуль, в основном не парах полукольцо - модуль Конвея - парах, состоящих из полукольца Конвея и полумодуля, удовлетворяющего тождествам "омега-сумма" и "омега-произведение". Они определены и сформулированы некоторые их важные свойства. Введены конечные автоматы над квемикольцами и доказана теорема Клини. Введены линейные системы над квемикольцами как обобщение регулярных грамматик с конечными и бесконечными выводами и связаны некоторые решения этих линейных систем с поведением конечных автоматов над квемикольцами.