Вестник БФУ им. И. Канта

2009 Выпуск №10

Назад к списку Скачать статью

Формальные языки и автоматы V: пары полукольцо-полумодуль Конвея и конечные автоматы

DOI
10.5922/2223-2095-2009-10-1
Страницы / Pages
6-41

Аннотация

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