Описание поведения конечного автомата (до 90 минут)

Для задания поведения конечного автомата (преобразователя) необходимо описать функцию , отображающую А* в В*(т.е. ). Эта функция может быть задана информационным деревом. Из каждой вершины информационного дерева исходят m ребер , взаимно-однозначно соответствующих буквам алфавита A. Каждой вершине приписано состояние автомата, а каждому ребру – буква алфавита B, следующим образом: корню приписано состояние q₀; если некоторой вершине приписано состояние q_i, то ребру, соответствующему букве a из A, приписана буква , а вершине, в которую ведет это ребро, приписано состояние . Каждому слову aÎA* соответствует единственная последовательность ребер этого дерева такая, что слово wÎB* совпадает со значением .

Для рассматриваемого примера имеем следующее поддерево информационного дерева: (левые ребра, исходящие из вершин соответствуют символу a₁, правые – символу a₂).

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

В рассматриваемом примере представимое событие (язык, множество слов) записывается как регулярное выражение в алгебре

, т.е.

Такие события могут быть также заданы как множества слов, порождаемых (выводимых) в некоторой формальной системе (ex, грамматике). Так, для автоматной (регулярной) грамматики <T,N,J,P> (здесь T и N соответственно терминальный и вспомогательный алфавиты, J – аксиом, т.е. JÎN, P – продукция вида B_i®aB_j, либо B_i®a)/ Слово a=a₁…a_n выводимо, если в P имеются правила J®a₁B_i2, B_i2®a₂B_i3, …, B_in®a_n

Лекция №7.

Описание КА микроподход

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

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

Текст лекции

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