Конечный автомат можно представлять несколькими способами:
- ориентированным графом (графом состояний), в котором
состояния есть вершины графа, а дуги есть переходы между
состояниями:
a3,V3
q2 q4
a1,V1
a5,V6
q1
a3,V5
a2,V2 q3 q5 q6
a4,V4 a7,V8
ai - символы входного алфавита, вызывающие переходы; Vi - символы выходного алфавита; qi - состояния автомата.
- таблицей переходов, в которой по строкам располагаются
состояния автомата, а по столбцам - символы входного алфавита. Клетки таблицы заполняют состояния, в которые переходит автомат под действием входных символов, а также символы выходного алфавита, соответствующие реакции автомата на входной символ. Например,
a1 | a2 | a3 | a4 | a5 | a6 | |
q1 начальное состояние | q2, V1 | q3, V2 | ||||
q2 | q4, V3 | |||||
q3 | q5, V4 | |||||
q4 | q5, V5 | q5, V6 | ||||
q5 | q6, V7 | |||||
q6 конечное состояние |
- матрицей переходов, которая представляет собой квадратную
|
|
матрицу, строки и столбцы которой соответствуют внутренним состояниям автомата. Клетки матрицы заполняются входными символами ak,при которых автомат переходит из состояния qi в состояние qj, а также выходными символами, соответствующими паре (ak, qi). Например,
q1 | q2 | q3 | q4 | q5 | q6 | |
q1 начальное состояние | a1, V1 | a2, V2 | ||||
q2 | a3, V3 | |||||
q3 | a4, V4 | |||||
q4 | a3, V5 a5, V6 | |||||
q5 | a6, V7 | |||||
q6 конечное состояние |
Определение. Детерминированным конечным автоматом называется такой автомат, каждая клетка таблицы переходов которого не содержит состояний больше одного. В противном случае автомат называется недетерминированным.
Определение. Конечный автомат называется полностью определенным, если его таблица переходов не содержит пустых клеток. Иначе автомат называют частично определенным.
Процедура приведения недетерминированного автомата
к детерминированному виду
1. В таблице переходов определяется клетка, в которой содержится более чем одно состояние, например, qi и qj.
2. Строка i и строка j накладываются друг на друга, и в таблице переходов появляется новая «склеенная» строка.
3. Если состояние qi или qj присутствует еще в какой-либо клетке таблицы переходов, то соответствующая строка i или j сохраняется в таблице, иначе удаляется после «склеивания».
Переход от не полностью определенного (частично определенного) автомата к полностью определенному в некоторых случаях может осуществляться заданием состояния ошибки, которое вносится во все пустые клетки таблицы.
|
|
Понятие изоморфизма двух автоматов
Пусть заданы два автомата:
ST ={ AT, QT, d T, l T, VT}, SR={ AR, QR, d R, l R,VR}.
Определение. Автоматы ST и SR изоморфны, если элементы множеств входных символов, выходных символов, состояний одного автомата можно переименовать так, что таблицы их переходов совпадут.
Определение. Пусть ST и SR - два автомата с одинаковыми входными и выходными алфавитами. Состояния qT и qR называются эквивалентными, если для любого a, где a - входной символ, справедливы равенства
lT (qT, a) = lR (qR, a), dT (qT, a) = dR (qR, a).
Определение. Состояние q’Î QT и q’’Î QR называются псевдо эквивалентными, если область определения q’ и q’’ одна и та же и в этой области q’ и q’’ эквивалентны.
Определение. Автоматы ST и SR называются псевдо эквивалентными, если для любого состояния автомата ST найдется псевдо эквивалентное состояние автомата SR и наоборот.
Замечание. Для полностью определенных автоматов отношение псевдо эквивалентности будет являться отношением эквивалентности.
Пример. Дляавтомата, заданного следующей таблицей переходов
a1 | a2 | a3 | |
q1 | 2,0 | - | 3,- |
q2 | - | 1,- | 3,0 |
q3 | 2,1 | 1,- | 3,0 |
определить наличие эквивалентных и псевдо эквивалентных состояний.
Решение. Рассмотрим состояния q2 и q 3 . Область определения для q2 принадлежит области определения q3. Кроме того на всей области определения q2 для " a имеют место равенства
l(q2, a) @ l(q3, a), d (q2, a) @ d (q3, a),
где ‘ @ ‘ - знак псевдоэквивалентности.
Состояние q3 может обрабатывать больше входных символов, чем состояние q2. Поэтому, если в автомате состояние q2 заменить состоянием q3, и переход в q2 заменить на переход в q3, то получим автомат с большими возможностями, чем предыдущий. В таком случае говорят, что q3 покрывает состояние q2.
Определение. Автомат ST покрывает автомат SR, если для " qi Î QR найдется состояние qi Î QT, покрывающее его.
Переход от автомата к покрывающему его автомату нельзя назвать эквивалентным преобразованием.