ТЕОРЕМА 7. 1
Множество функций, вычисляемых конечными автоматами, замкнуто относительно операции суперпозиции.
Доказательство
Пусть f: A* ® B* и g: B* ® C* - словарные функции, вычисляемые автоматами Â и Á из состояний и соответственно.
Рассмотрим устройство, получаемое подключением выхода автомата Â к входу автомата Á, как это изображено на рис. 7.5
 Á
C
Рис.7.5
Это устройство называется суперпозицией автоматов ÂиÁ. Входным и выходным алфавитами автомата C являются множества A и C. Множество состояний автомата C состоит из всевозможных пар ( , ), где - состояние Â, а - состояние Á. Работа автомата C в каждый момент времени связана с переработкой очередного входного символа aÎA из текущего состояния ( , ), при котором сначала автомат  перерабатывает a во входной символ автомата Á, который перерабатывает его в выходной символ, автомата C. Измененение состояния C состоит в изменении состояний  и Á под действием входных символов автоматов ÂиÁ.
Тогда C является автоматом, который вычисляет функцию g f из начального состояния ( , ).
Дата добавления: 2015-09-18; просмотров: 597;