Презентация на тему Абстрактный автомат. Описание автомата

удобно описывать с помощью таблиц, а для наглядности использовать

графы

одна из которых раскрывает функцию переходов (см. таблицу 1.1),

а другая - функцию выходов (см. таблицу 1.2)
Число строк таблиц 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) (см. таблицу 1.3)
В позициях этой таблицы записывают пары (q[τ+1], y[τ]) для каждой пары (q[τ], x[τ])

Таблица 1.1 – Функция переходов

Таблица 1.2 – Функция выходов

автомата Мили
Поэтому таблица 1.3 описывает поведение автомата Мили
Таблица автомата

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

Таблица 1.3

Таблица 1.4

проектирования автоматов встречаются случаи, когда функции переходов и/или выходов

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

Таблица 1.1 – Функция переходов

Таблица 1.2 – Функция выходов

Мура
Таблица 1.7
Таблица 1.8

автомата удобно анализировать с помощью графов, вершинами которого являются

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

описание соединений состояний автомата Мили
Таблицей 1.10 - автомата

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

Таблица 1.9

Таблица 1.10

автомата следует соблюдать следующие условия:
для каждого символа x∈X есть

дуга, исходящая из вершины q∈Q
каждый символ x∈X у каждой вершины-истока q∈Q принадлежит только одной дуге
если между двумя вершинами q∈Q существует несколько дуг, что может быть обусловлено переходом автомата из состояния qs∈Q в состояние qt∈Q при различных символах на входе, то есть xi ≠xj, то эти дуги могут быть заменены одной дугой с указанием дизъюнктивной связи этих состояний например
если yu≠yv, то на дуге следует указать (xi/yu ∨ xj/ yv)
если yu=yv=y, то - (xi∨xj)/y)