2015-06-28
318
1 Выполним процедуру преобразования НКА в КА по описанному выше алгоритму(см. рис а на следующей стр.)
2 Переобозначим состояния следующим образом(см. рис. б):
a = { A, B }; b = { B, C }; c = { B }; d = { A, C }; e = { C };
f = { A }; g = { A, B, C }.
а (до переобозначения) б (после переобозначения)
| S | k | n | –| | S | k | n | –| | |
| A,B | A,B | B,C | a | a | b | |||
| B,C | B | A,C | b | c | d | |||
| B | B | C | c | c | e | |||
| A,C | A | A,B,C | d | f | g | |||
| C | A,C | e | d | |||||
| A | A | B,C | f | f | b | |||
| A,B,C | A,B | A,B,C | g | a | g |
3 Проверим состояния полученного КА на достижимость:
{a} à{a,b} à {a, b, c, d} à {a, b, c, d, e,f, g}
Все состояния КА достижимы.
4 Проверим состояния полученного КА на эквивалентность:
Первое разбиение множества состояний на подмножества по входному символу "конец цепочки": {f}; {a,b,c,d,e,g}.
Проанализируем воздействие входного символа " k " на второе подмножество:
d à f; e à { }; остальные остаются в этом же подмножестве. Есть основания выделить d и e в отдельные подмножества.
Теперь разбиение будет иметь вид: { f}; {d}; {e}; {a,b,c,g}.
|
|
|
Проанализируем воздействие входного символа " n " на последнее подмножество:
b à d; c à e; a à b; g à g.
Состояния b и c переходят в другие группы и их нужно выделить; состояние а – в выделенное на этом шаге состояние b и на этом основании его тоже нужно выделить. В результате:
{f}; {d}; {e}; {a}; {b}; {c}; {g}.
Вывод: эквивалентных состояний нет; полученный КА является минимальным.
5 По таблице переходов КА определим остальные его параметры:
V = { k, n, –| }; S нач ={a}; S доп = {a, b, c, d, e, g};
S = {a, b, c, d, e, f, g}.
4.5 Задачи к главе 4
1 Построить с полным описанием конечный автомат для распознания цепочек в алфавите V={0,1,2}, которые начинаются на 0 и в цепочке встречается ровно два символа 2.
2 Построить с полным описанием конечный автомат для распознания цепочек в алфавите V={a, b, c}, которые содержат символ b только парами и заканчиваются на c.
3 Построить с полным описанием конечный автомат для распознания цепочек в алфавите V={а, b, c}, которые начинаются с b и в цепочке встречается только один раз ac.
4 Построить с полным описанием конечный автомат для распознания цепочек в алфавите V={0,1}, которые начинаются с 11 и в цепочке нули стоят только по два.
5 Определить эквивалентные и недостижимые состояния КА. Построить минимальный КА и диаграмму переходов для полученного минимального КА.
A б в
| a | b | –| | a | b | –| | a | b | –| | |||||
| A | F | B | A | C | E | A | A | D | |||||
| B | E | F | B | D | A | B | C | F | |||||
| C | F | A | C | A | F | C | B | F | |||||
| D | B | B | D | C | E | D | B | A | |||||
| E | B | D | E | F | D | E | D | F | |||||
| F | E | E | F | E | D | F | A | C |
Г д е
|
|
|
| a | b | -| | a | b | -| | a | b | -| | |||||
| A | F | B | A | B | D | A | C | D | |||||
| B | B | F | B | A | F | B | D | A | |||||
| C | F | A | C | B | D | C | D | F | |||||
| D | E | B | D | C | A | D | C | E | |||||
| E | E | F | E | D | F | E | F | C | |||||
| F | E | B | F | B | A | F | E | D |
6 Преобразовать заданный НКА в КА и выполнить процедуру минимизации КА.
А б
| -| | -| | |||||||
| àA | B | A,C | A | B | C | |||
| àB | A | B | B | A,B | ||||
| C | C | A | àC | A | C |
В г
| -| | a | b | -| | |||||
| àA | B | C | àA | A | B,C | |||
| B | A,B | C | àB | C | A | |||
| C | B | A | C | A,C |
Д е
| a | b | -| | –| | ||||||
| àA | A | C | àA | A,B | B | A,C | |||
| B | A | A,B | B | A | B | A | |||
| àC | B | A,C | C | A | C | C |
Ж з
| -| | -| | |||||||
| àA | A | B,C | àA | A,C | B,C | |||
| B | B | C | àB | A | C | |||
| àC | A,C | C | B | B |
И к
| а | b | -| | -| | |||||
| A | A | D | àA | B | A,C | |||
| àB | B | C | B | B | C | |||
| C | C | D | C | C | A,C | |||
| D | A,D | D |
5 Автоматы с магазинной памятью
5.1 Автоматы-распознаватели с магазинной памятью
Далеко не для всех регулярных множеств можно построить КА –распознаватель, так как КА не имеет возможности считать и запоминать количество символов обрабатываемой цепочки. Для этой цели используется специальное устройство – магазин, в который можно помещать символы или удалять их, запоминая или сравнивая количество символов входной цепочки. Такой автомат называется автоматом – распознавателем с магазинной памятью (сокращенно – МП –автомат).
МП – автомат задается:
1 конечным множеством входных символов (включая символ конца цепочки "–|");
2 конечным множеством магазинных символов (включая маркер дна магазина – #);
3 конечным множеством состояний;
4 управляющей таблицей, которая каждой комбинации трех параметров: входной символ, магазинный символ(верхний символ магазина), состояние – ставит в соответствие действие с магазином, входным символом, и состоянием;
5 начальной конфигурацией (начальное состояние и начальное содержимое магазина);
6 множеством допускающих конфигураций (комбинаций – состояние МП–автомата и верхний символ магазина в момент, когда приходит символ "конец цепочки").
Большинство ячеек управляющей таблицы имеют вид, показанный на рисунке: ячейка разбита на три поля; в левом поле указывается новое состояние МП – автомата, в центральном – действия с магазином, в правом – действия с входным символом.
 |
Ряд ячеек управляющей таблицы, при необходимости, без деления на поля может быть заполненным символом Е (состояние ошибки). Если МП – распознаватель попал в такое состояние, то обработка цепочки прекращается и такая цепочка отвергается.
