Формальные языки и автоматы V: пары полукольцо-полумодуль Конвея и конечные автоматы
АннотацияЭто пятая статья в серии, дающей обзор некоторых разделов теории формальных языков и автоматов с использованием полуколец, формальных степенных рядов, матриц и теории неподвижных точек. Рассмотрены основные результаты теории конечных автоматов над квемикольцами, обобщающих классические конечные автоматы, принимающие конечные и бесконечные слова, базирующиеся на парах полукольцо - полумодуль, в основном не парах полукольцо - модуль Конвея - парах, состоящих из полукольца Конвея и полумодуля, удовлетворяющего тождествам "омега-сумма" и "омега-произведение". Они определены и сформулированы некоторые их важные свойства. Введены конечные автоматы над квемикольцами и доказана теорема Клини. Введены линейные системы над квемикольцами как обобщение регулярных грамматик с конечными и бесконечными выводами и связаны некоторые решения этих линейных систем с поведением конечных автоматов над квемикольцами.