Часть 3. Математические модели

О мощности порождающих множеств в классе автоматов с линейной функцией выходов

Ф. Р. Юсупов

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

Аннотация: Класс конечных автоматов конечно порожден по операциям композиции [1]. Важными его подклассами являются классы автоматов с линейными функциями выходов. Набор операций над автоматами, состоящий из подстановки переменных, подстановки автоматов и обратной связи, мы называем ограниченной композицией. По операциям ограниченной композиции класс одноместных автоматов замкнут. В настоящей работе показано, что в классе одноместных конечных автоматов с линейными функциями выходов и операциями ограниченной композиции отсутствуют конечные полные множества, но автоматы из этого класса, реализуемые схемами с не более чем одной задержкой, порождают этот класс.

Ключевые слова: конечные автоматы, операции композиции для автоматов, конечные автоматы с линейными выходами.