Описание конечного автомата

Автоматы удобно описывать с помощью таблиц, а для наглядности использовать графы. При табличном описании задают две таблицы, одна из которых раскрывает функцию переходов QX)Q а другая - функцию выходов QX)Y Число строк таблиц m равно числу состояний автомата, т.е. m = Q . Число столбцов таблиц n равно числу символов входного алфавита, т.е. n = X . В позиции первой таблицы записывают значения очередных состояний автомата q[1]Q, в которые он переходит для каждой пары (q[];x[])QX). В позиции второй таблицы записывают значения символов выходного алфавита y[]Y, которые генерирует автомат для каждой пары (q[];x[])QX). Если в таблицах 1 и 2 определены значения q[1]Q и y[]Y для каждой пары (q[];x[])QX), то есть заполнены все позиции таблиц, то дано описание детерминированного автомата.

Обычно эти таблицы совмещают в одну, которая раскрывает оператор поведения : QX) QY) В позициях этой таблицы записывают пары (q[1];y[]) для каждой пары (q[];x[]).

Таблицы абстрактного автомата совпадают с таблицами автомата Мили. Поэтому таблица 3 описывает поведение автомата Мили. Таблица автомата Мура (см. таблицу 4) несколько отличается от таблицы автомата Мили, так как QY. Значение выходного символа приписывают, как метку, состоянию автомата. Описание С-автомата есть объединение таблиц 3 и 4. Так как в таблицах 3 и 4 определены все позиции, то такими таблицами дано описание детерминированных автоматов.

В практике проектирования автоматов встречаются случаи, когда функции переходов и/или выходов не определены для некоторых значений символов входного алфавита. В этом случае говорят, что автомат недетерминированный или частично определенный. При описании таких автоматов неопределенные позиции таблиц помечаются символом "_*". Например, в таблицах 5, 6, 7 и 8 приведено описание недетерминированных автоматов.

Поведение автомата удобно анализировать с помощью графов, вершинами которого являются элементы множества qQ. Тогда вершина-исток есть образ текущего состояния q[], а вершина-сток - образ очередного состояния q[1]. Дуги отображают переход автомата из одного состояния в другое (q[];q[1]) под воздействием x[]X.Для описания автомата с помощью графов удобно воспользоваться таблицами соединений состояний автомата. Строки и столбцы такой таблицы представляют символы qQ .Следовательно, число строк и столбцов таблицы равно m. Строки этой таблицы характеризуют текущее состояние, т.е. q[], а столбцы - очередное, т.е. q[1]. Позиции таблицы заполняют значениями пары (x[]/y[]) для соответствующего перехода автомата из текущего состояния в очередное.

Таблицей 9 дано описание соединений состояний автомата Мили, а таблицей 10 - автомата Мура. Для автомата Мили на дугах графа указывают пару (входной символ/выходной символ). Для автомата Мура на дугах графа указывают только входной символ, определяющий переход автомата из одного состояния в другое, а выходной символ y, приписывают к каждой вершине графа.

При начертании графа детерминированного автомата следует соблюдать следующие условия:1) для каждого символа xX есть дуга, исходящая из вершины qQ; 2) каждый символ xX у каждой вершины-истока qQ принадлежит только одной дуге; 3) если между двумя вершинами qQ существует несколько дуг, что может быть обусловлено переходом автомата из состояния q_sQ в состояние q_tQ при различных символах на входе, то есть x_i ¹x_j, то эти дуги могут быть заменены одной дугой с указанием дизъюнктивной связи этих состояний (например, если y_u¹y_v, то на дуге следует указать (x_i/y_ux_j/y_v);.если y_u=y_v=y, то - (x_ix_j)/y).

Дата добавления: 2015-07-26; просмотров: 281; Нарушение авторских прав

Мы поможем в написании ваших работ!