Типы конечных автоматов

По способу формирования функций выхода выделяют автоматы Мили и Мура.

В автомате Мили функция выходов j определяет значение выходного символа по классической схеме абстрактного автомата. Математическая модель автомата Мили и схема рекуррентных соотношений не отличаются от математической модели и схемы рекуррентных соотношений абстрактного автомата, т.е.

(1.12)

(1.13)

Особенностью автомата Мили является то, что функция выходов является двухаргументной и символ в выходном канале y[t] обнаруживается только при наличии символа во входном канале x[t]. Функциональная схема не отличается от схемы абстрактного автомата (см. рис 1.2 и 1.3).

Рис. 1.3. Функциональная схема автомата Мили.

В автомате Мура функция j определяет значение выходного символа только по одному аргументу - состоянию автомата. Эту функцию называют также функцией меток, так как она каждому состоянию автомата ставит метку на выходе. Математическая модель и схема рекуррентных соотношений автомата Мура имеют вид:

(1.14)

(1.15)

Особенностью автомата Мура является то, что символ y[t] в выходном канале существует все время пока автомат находится в состоянии q[t]. Функциональная схема автомата Мура представлена на рис. 1.4.

Рис. 1.4. Функциональная схема автомата Мура.

Объединение автоматов Мили и Мура представляет С-автомат, для которого схема рекуррентных соотношений имеет вид:

(1.16)

Потребность такого автомата возникает при формировании автоматных сетей (см. 2).

Функциональная схема С-автомата представлена на рис.1. 5.

Рис.1. 5. Функциональная схема С-автомата.

Интересно выделить особые классы автоматов, математические модели которых опираются только на два носителя алгебры.

Пусть X=Æ. Тогда математическая модель и система рекуррентных соотношений имеют вид:

(1.17)

(1.18)

Функциональная схема автомата приведена на рис.1.6.

Рис.1.6. Функциональная схема порождающего автомата.

Особенностью функционирования такого автомата является генерация последовательности символов выходного слова только в зависимости от последовательности состояний автомата. Такие автоматы называют порождающими или автономными. С помощью такого автомата генерируется последовательность управляющих команд на какие-либо объекты внешней среды.

Пусть Y=Æ. Тогда математическая модель и система рекуррентных соотношений имеют вид:

(1.19)

q[t+1] = y(q[t];x[t]); (1.20)

Функциональная схема автомата приведена на рис.1.7.

Рис. 1.7. Функциональная схема распознающего автомата.

Особенностью функционирования такого автомата является распознавание в последовательности изменений аргумента функции переходов значения (q_i[t];x_i[t]) и перевод автомата в заключительное состояние q_k. С помощью такого автомата обнаруживают заданные возмущения со стороны объектов внешней среды или распознают заданную последовательность входных символов. Поэтому такие автоматы называютраспознающими. Часто и автомат Мура представляют автоматом без выхода, так как его выходной сигнал эквивалентен состоянию автомата.

Пусть Q=Æ. Тогда математическая модель и система рекуррентных соотношений имеют вид:

(1.21)

y[t] = j(x[t]); (1.22)

Функциональная схема автомата приведена на рис.8.

Рис. 1.8. Функциональная схема комбинационного автомата.

Особенностью функционирования такого автомата является отсутствие "памяти", т.е. на каждый символ входного алфавита автомат генерирует символ выходного алфавита без учета состояния автомата. Такие автоматы чаще всего называют комбинационными автоматами.

Контрольные вопросы.

1) Объясните математическую модель автомата Мили.

2) Объясните математическую модель автомата Мура.

3) Что такое "порождающий автомат"? Где находит применение?

4) Что такое "распознающий автомат"? Где находит применение?

5) Что такое комбинационный автомат? Где находит применение?

1.3. Описание автомата

Автоматы удобно описывать с помощью таблиц, а для наглядности использовать графы. При табличном описании задают две таблицы, одна из которых раскрывает функцию переходов y: (QÄX)® Q (см. таблицу 1.1), а другая - функцию выходов j: (QÄX)® Y (см. таблицу 1.2). Число строк таблиц m равно числу состояний автомата, т.е. m = êQ ê. Число столбцов таблиц n равно числу символов входного алфавита, т.е. n = êX ê. В позиции первой таблицы записывают значения очередных состояний автомата q[t+1]ÎQ, в которые он переходит для каждой пары (q[t];x[t])Î(QÄX). В позиции второй таблицы записывают значения символов выходного алфавита y[t]ÎY, которые генерирует автомат для каждой пары (q[t];x[t])Î(QÄX). Если в таблицах 1 и 2 определены значения q[t+1]ÎQ и y[t]ÎY для каждой пары (q[t];x[t])Î(QÄX), то есть заполнены все позиции таблиц, то дано описание детерминированного автомата.

Обычно эти таблицы совмещают в одну, которая раскрывает оператор поведения (y;j): (QÄX) ® (QÄY) (см. таблицу 1.3). В позициях этой таблицы записывают пары (q[t+1];y[t]) для каждой пары (q[t];x[t]).

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

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

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

Таблицей 1.9 дано описание соединений состояний автомата Мили, а таблицей 1.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).

Пример 1.1. Детерминированный автомат Мили задан таблицей 1.11.

Таблица 1.11.

Составить таблицу соединения состояний автомата и начертить граф. Найти генерируемые автоматом слова b для различных начальных состояний, если на входе автомата задано слово a = (x₁x₂x₃x₄x₄x₃x₂x₁).

Для формирования таблицы соединения состояний автомата находим по таблице 1.11 число строк и столбцов. Это число равно 4. Имена строк и столбцов заданы именами элементов множества qÎQ. В позициях таблицы будут значения (x/y), соответствующие переходу из состояния q[t] в состояние q[t+1]. Следует обратить внимание, что переход из состояния q₃ в q₂ обусловлен двумя входными символами (x₁ и x₄), а для каждой пары (q₃;x₁) и (q₃;x₄) автомат генерирует в выходном канале особый символ (y₁ и y₃). Поэтому на дуге (q₃;q₂) следует указать (x₁/y₁Úx₄/y₃). Переход из состояния q₄ в q₁ обусловлен также двумя входными символами (x₂ и x₄), но автомат генерирует только один символ на выходе y₁. Поэтому на дуге (q₄;q₁) следует указать (x₂Úx₄)/y₁. Остальные переходы автомата обусловлены появлением только одного входного символа. Таблица 1.12 представляет таблицу соединений состояний автомата Мили, а рис. 9 – его граф.

Таблица 1.12.

Рис.1.9. Граф детерминированного автомата Мили.

Для поиска слов b при различных начальных условиях необходимо проследить всю последовательность изменения состояний автомата для каждого очередного символа слова a:

пусть q₁=q₀, тогда

a[t]: x₁[1] x₂[2] x₃[3] x₄[4] x₄[5] x₃[6] x₂[7] x₁[8]

q[t+1]: q₁[1] q₂[2] q₄[3] q₂[4] q₂[5] q₂[6] q₁[7] q₃[8] q₂[9]

b[t]: y₁[1] y₁[2] y₂[3] y₂[4] y₂[5] y₂[6] y₁[7] y₁[8],

то есть b=(y₁y₁y₂y₂y₂y₂y₁y₁);

пусть q₂=q₀, тогда

a[t]: x₁[1] x₂[2] x₃[3] x₄[4] x₄[5] x₃[6] x₂[7] x₁[8]

q[t+1]: q₂[1] q₃[2] q₃[3] q₁[4] q₁[5] q₁[6] q₄[7] q₁[8] q₂[9]

b[t]: y₃[1] y₂[2] y₁[3] y₃[4] y₃[5] y₁[6] y₁[7] y₁[8],

то есть b=(y₃y₂y₁y₃y₃y₁y₁y₁);

пусть q₃=q₀, тогда

a[t]: x₁[1] x₂[2] x₃[3] x₄[4] x₄[5] x₃[6] x₂[7] x₁[8]

q[t+1]: q₃[1] q₂[2] q₄[3] q₂[4] q₂[5] q₂[6] q₁[7] q₃[8] q₂[9]

b[t]: y₁[1] y₁[2] y₂[3] y₂[4] y₂[5] y₂[6] y₁[7] y₁[8],

то есть b=(y₁y₁y₂y₂y₂y₂y₁y₁);

пусть q₄=q₀, тогда

a[t]: x₁[1] x₂[2] x₃[3] x₄[4] x₄[5] x₃[6] x₂[7] x₁[8]

q[t+1]: q₄[1] q₄[2] q₁[3] q₄[4] q₁[5] q₁[6] q₄[7] q₁[8] q₂[9]

b[t]: y₂[1] y₁[2] y₁[3] y₁[4] y₃[5] y₁[6] y₁[7] y₁[8],

то есть b=(y₂y₁y₁y₁y₃y₁y₁y₁).

Анализ показывает, что при различных начальных состояниях реакция автомата на одинаковые слова различна. Это подтверждает необходимость указания начального состояния q_i=q₀. Только в этом случае каждому слову на входе автомата найдется единственный образ на выходе.

Пример 1.2. Детерминированный автомат Мура задан таблицей поведения (см.таблицу 13).

Таблица 1.13.

Составить таблицу соединения состояний автомата и начертить граф. Найти генерируемые автоматом слова b для различных начальных состояний, если на входе автомата задано слово a = (x₁x₂x₃x₄x₄x₃x₂x₁).

Для формирования таблицы соединения состояний автомата находим по таблице 1.13 число строк и столбцов. Это число равно 4. Имена строк и столбцов заданы именами элементов множества qÎQ. Элементами таблицы соединения состояний автомата будут значения x, соответствующие переходу из состояния q[t] в состояние q[t+1]. Переход из состояния q₃ в q₂ обусловлен двумя входными символами (x₁ и x₄). Поэтому на дуге (q₃;q₂) cледует указать (x₁Úx₄). Переход из состояния q₄ в q₁ обусловлен также двумя входными символами (x₂ и x₄). Поэтому на дуге (q₄;q₁) cледует указать (x₂Úx₄). Таблица 1.14 представляет таблицу соединений состояний автомата Мура, а рис.1.10 - его граф.

Tаблица 1.14

Рис.1.10 Граф детерминированного автомата Мура.

Для поиска слов b при различных начальных условиях необходимо проследить всю последовательность изменения состояний автомата для каждого очередного символа слова a:

пусть q₁=q₀, тогда

a[t]: x₁[1] x₂[2] x₃[3] x₄[4] x₄[5] x₃[6] x₂[7] x₁[8]

q[t+1]: q₁[1] q₂[2] q₄[3] q₂[4] q₂[5] q₂[6] q₁[7] q₃[8] q₂[9]

b[t]: y₁[1] y₃[2] y₁[3] y₃[4] y₃[5] y₃[6] y₁[7] y₂[8],

то есть b=(y₁y₃y₁y₃y₃y₃y₁y₂);

пусть q₂=q₀, тогда

a[t]: x₁[1] x₂[2] x₃[3] x₄[4] x₄[5] x₃[6] x₂[7] x₁[8]

q[t+1]: q₂[1] q₃[2] q₃[3] q₁[4] q₁[5] q₁[6] q₄[7] q₁[8] q₂[9]

b[t]: y₃[1] y₂[2] y₂[3] y₁[4] y₁[5] y₁[6] y₁[7] y₁[8],

то есть b=(y₃y₂y₂y₁y₁y₁y₁y₁);

пусть q₃=q₀, тогда

a[t]: x₁[1] x₂[2] x₃[3] x₄[4] x₄[5] x₃[6] x₂[7] x₁[8]

q[t+1]: q₃[1] q₂[2] q₄[3] q₂[4] q₂[5] q₂[6] q₁[7] q₃[8] q₂[9]

b[t]: y₂[1] y₃[2] y₁[3] y₃[4] y₃[5] y₃[6] y₁[7] y₂[8],

то есть b=(y₂y₃y₁y₃y₃y₃y₁y₂);

пусть q₄=q₀, тогда

a[t]: x₁[1] x₂[2] x₃[3] x₄[4] x₄[5] x₃[6] x₂[7] x₁[8]

q[t+1]: q₄[1] q₄[2] q₁[3] q₄[4] q₁[5] q₁[6] q₄[7] q₁[8] q₂[9]

b[t]: y₁[1] y₁[2] y₁[3] y₁[4] y₁[5] y₁[6] y₁[7] y₁[8]

то есть b=(y₁y₁y₁y₁y₁y₁y₁y₁).

Этот пример также подтверждает необходимость указания начального состояния q=q₀.

Пример 1.3. Недетерминированный автомат Мили задан таблицей поведения (см. таблицу 1.15).

Составить таблицу соединения состояний автомата и начертить граф. Найти генерируемые автоматом слова b для различных a и различных начальных состояний.

Элементами таблицы соединения состояний автомата будут значения (x/y), соответствующие переходу из состояния q[t] в состояние q[t+1]. Следует обратить внимание, что не определены переходы из состояния q₂ для входного символа x₁, из состояния q₃ для входного символа x₂ и из состояния q₄ для входного символа x₄.

Не определены также значения символов на выходе для состояния q₁ и входного символа x₂, для состояния q₂ и входного символа x4 и для состояния q₃ и входного символа x₂. Таблица 1.16 представляет таблицу соединений состояний недетерминированного автомата Мили, а рис.11 - его граф.

Таблица 1.15.

Таблица 1.16.

Для поиска слов b, генерируемых недетерминированным автоматом Мура также необходимо проследить последовательность изменения состояний автомата для каждого очередного символа слова a:

пусть q₁=q₀ и a= (x₁x₂x₃x₃x₃x₂x₄x₄), тогда

a[t]: x₁[1] x₂[2] x₃[3] x₃[4] x₃[5] x₂[6] x₄[7] x₄[8]

q[t+1]: q₁[1] q₂[2] q₄[3] q₂[4] q₁[5] q₄[6] q₁[7] q₁[8] q₁[9]

b[t]: y₁[1] y₁[2] y₂[3] y₂[4] y₁[5] y₁[6] y₃[7] y₃[8],

то есть b=(y₁y₁y₂y₂y₁y₁y₃y₃);

Рис.1.11 Граф недетерминированного автомата Мили.

пусть q₁=q₀ и a= (x₂x₂x₃x₄x₄x₃x₂x₁), тогда

a[t]: x₂[1] x₂[2] x₃[3] …

q[t+1]: q₁[1] q₃[2] _* …

b[t]: _*[1] _*[2] …,

то есть b= (_{* *} … и автомат "зависает" на третьем символе слова a;

пусть q₁=q₀ и a= (x₂x₂x₃x₄x₄x₃x₂x₁), тогда

a[t]: x₁[1] x₄[2] x₃[3] x₂[4] x₃[5] x₂[6] x₄[7] x₄[8]

q[t+1]: q₁[1] q₂[2] q₂[3] q₁[4] q₃[5] q₁[6] q₃[7] q₂[8] q₂[9]

b[t]: y₁[1] _*[2] y2[3] _* [4] y1[5] _* [6] y₃[7] _* [8],

то есть b=(y_1*y_2*y_*y_*) содержит четыре символа "_*";

пусть q₂=q₀ и a= (x₁x₄x₃x₂x₃x₂x₄x₄), тогда

a[t]: x₁[1] x₄[2] …

q[t+1]: q₂[1] _*.[2] …

b[t]: y₃[1] …

то есть b= (y₃ … и автомат "зависает" на втором символе слова a.

Анализ показывает, что недетерминированный автомат Мили может

1) генерировать на выходе последовательности символов, равные последовательностям символов на входе, но содержащие неопределенные символы "_*", что разрушает образ слова a;

2) "зависать" в состоянии, для которого не определен переход в очередное состояние.

Пример 1.4. Недетерминированный автомат Мура задан таблицей поведения (см. таблицу 1.17).

Таблица 1.17.

Составить таблицу соединения состояний автомата и начертить граф. Найти генерируемые автоматом слова b для различных a и различных начальных состояний.

Элементами таблицы соединения состояний автомата будут значения x, соответствующие переходу из состояния q[t] в состояние q[t+1]. Следует обратить внимание, что не определены переходы из состояния q₂ для входного символа x₁, из состояния q₃ для входного символа x₂ и из состояния q₄ для входного символа x₄. Не определено также значение символа на выходе для состояния q₂. Таблица 1.18 представляет таблицу соединений состояний недетерминированного автомата Мура, а рис.1.12 - его граф.

Таблица 1.18.

Рис.1.12. Граф недетерминированного автомата Мура.

Для поиска слов b при различных начальных условиях необходимо проследить всю последовательность изменения состояний автомата для каждого очередного символа слова a:

пусть q₁=q₀ и a= (x₂x₃x₂x₃x₃x₁x₂x₄), тогда

a[t]: x₂[1] x₃[2] x₂[3] x₃[4] x₃[5] x₁[6] x₂[7] x₄[8]

q[t+1]: q₁[1] q₃[2] q₁[3] q₃[4] q₁[5] q₄[6] q₄[7] q₁[8] q₁[9]

b[t]: y₁[1] y₂[2] y₁[3] y₂[4] y₁[5] y₁[6] y₁[7] y₁[8],

то есть b= (y₁y₂y₁y₂y₁y₁y₁y₁);

пусть q₂=q₀ и a= (x₂x₃x₁x₄x₄x₃x₂x₁), тогда

a[t]: x₂[1] x3[2] x₁[3] x₄[4] …

q[t+1]: q₂[1] q₄[2] q₂[3] _* [4] …

b[t]: _* [1] y₁[2] _* [3] …,

то есть b= (_*y_1* … и автомат "зависает" на четвертом символе слова a;

пусть q₁=q₀ и a= (x₁x₂x₃x₃x₁x₃x₁x₃), тогда

a[t]: x₁[1] x₂[2] x₃[3] x₃[4] x₁[5] x₃[6] x₁[7] x₃[8]

q[t+1]: q₁[1] q₂[2] q₄[3] q₂[4] q₁[5] q₂[6] q₁[7] q₂[8] q₁[9]

b[t]: y₁[1] _*[2] y₁[3] _* [4] y₁[5] _* [6] y₁[7] _* [8],

то есть b=(y_1*y_1*y_1*y_1*) содержит четыре символа про"_*";

пусть q₂=q₀ и a= (x₁x₄x₃x₂x₃x₂x₄x₄), тогда

a[t]: x₁[1] x₄[2] …

q[t+1]: q₂[1] _* [2] …

b[t]: _* …,

то есть b= (_* … и автомат "зависает" на втором символе слова a.

Анализ показывает, что для недетерминированного автомата Мура характерны такие же недостатки, как для недетерминированного автомата Мили.

Контрольные вопросы и задачи

1) Объясните таблицы переходов, выхода, поведения и соединения состояний детерминированного автомата Мили.

2) Объясните таблицы переходов, выхода, поведения и соединения состояний детерминированного автомата Мура.

3) Объясните таблицы переходов, выхода, поведения и соединения состояний недетерминированного автомата Мили.

4) Объясните таблицы переходов, выхода, поведения и соединения состояний недетерминированного автомата Мура.

5) Описать автомат М с алфавитом X=Y={0;1}, который, исходя из начального состояния q₀, перерабатывает входную последовательность a в задержанную на два такта последовательность b=(00a).

6) Начертить граф автомата, таблица поведения которого имеет вид:

7) Описать автомат М с двумя состояниями, который переводит десятичные цифры 0,1, …,9 поданные на вход, в двоичные последовательности 0000,0001, …,1001 соответственно, а двоичные последовательности 0000,0001, …,1111,- в десятичные записи 0,1, …,15 соответственно.

8) Описать автомат М с алфавитом X=Y={0;1}, который печатает на выходе "1, если непосредственно перед этим он считал четыре "1" последовательно, в противном случае печатает "0". Автомат работает до тех пор, пока не считает три "0" последовательно, после чего печатает лишь "0".

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

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