Тернарное отношение (до 70 минут)

,

где - слова, соответственно в алфавите A,Q,B, называется функционированием конечного автомата >A,Q,B, d, l> (q₀ – начальное состояние, q₀ÎQ).

Правила функционирования конечного автомата определяют его работу в дискретные моменты времени t=1,2,3,...

Пусть - соответственно входной символ, символ внутреннего состояния и выходной символ в момент t=1,2,3,... Тем самым автомат можно рассматривать как динамическую систему, в которой текущая точка траектории имеет координаты < > (для определенности рассматривается общий случай; в частных случаях – автомата без входа, без выхода и т.д. фигурирует лишь часть этих координат) Очевидно, что координаты текущей точки должны удовлетворять рекуррентным состояниям автоматов 1-го и 2-го родов.

В динамических системах такого типа воплощается вся информация о поведении инициального (настроенного) автомата, содержащаяся в правилах его функционирования. Правила координирования интерпретируют траекторию (конечную или бесконечную):

< >, < >,...< >,... как вычислительный процесс одного из трех типов (ниже a и w могут быть конечными и бесконечными словами соответственно в алфавитах А и В):

1) преобразующий процесс, в котором происходит преобразование некоторого слова a в слово (словарная функция называется вычислимым или реализуемым инициальным конечным автоматом оператором);

2) Распознающий процесс, в котором для некоторого слова aÎА* выясняется, обладает ли оно предъявляемым признаком, который распознается автоматом (иначе говоря, принимается ли слово a автоматом);

3) порождающий процесс, в котором строится некоторое слово wÎB*/

Поведение инициального конечного автомата обычно называют одно из следующих трех выражений:

1) ;

2) ;

3) .

Конечный автомат с поведением типа 1) называется конечным преобразователем, а с поведением типа 2) – акцептором или конечным распознавателем (множество L_F называют событием представимым акцептором с множеством заключительных состояний F). Поведение типа 3), т.е. множество значений словарной функции (перечисляемое множество), характеризует порождающий конечный автомат (генератор).

Замечание: 1). Конечный автомат и его функционирование могут быть определены различными эквивалентными способами (основные из которых рассмотрены далее); 2). L_F часто называют рекуррентным множеством.

Лекция №5.

-Способы задания КА, макроподход.

Продолжительность: 2 часа (90) минут

Ключевые (основные) вопросы (моменты)

-функционирование КА

-диаграмма, автоматная таблица, диаграмма переходов.

Текст лекции

Дата добавления: 2015-12-01