2014-02-18
777
И к
Ж з
Д е
В г
А б
Г д е
A б в
Р е ш е н и е
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 | 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 множеством допускающих конфигураций (комбинаций – состояние МП–автомата и верхний символ магазина в момент, когда приходит символ "конец цепочки").
Большинство ячеек управляющей таблицы имеют вид, показанный на рисунке: ячейка разбита на три поля; в левом поле указывается новое состояние МП – автомата, в центральном – действия с магазином, в правом – действия с входным символом.
 |
Ряд ячеек управляющей таблицы, при необходимости, без деления на поля может быть заполненным символом Е (состояние ошибки). Если МП – распознаватель попал в такое состояние, то обработка цепочки прекращается и такая цепочка отвергается.
Допускаемые операции с входными символами
1 Держать текущий входной символ обрабатываемой цепочки (Д).
2 Перейти к следующему символу обрабатываемой цепочки (П).
Примечание. Запрещен переход к следующему символу, если текущий символ –| ("конец цепочки").
Допускаемые операции над магазином
Магазин можно представить в виде одностороннего стека или упорядоченного списка, в котором доступен для выполнения действий только первый(верхний) символ. При вталкивании нового символа в магазин все, находящиеся до этого в магазине символы, смещаются на одну позицию (для определенности вправо). Доступ возможен только к верхнему символу магазина. С ним и выполняются операции, указанные в управляющей таблице:
1 Втолкнуть в магазин магазинный символ, к примеру А (Вт.А).
2 Вытолкнуть из магазина верхний символ, к примеру А (Выт.А).
3 Оставить магазин без изменений (О).
Примечания:
1 Запрещено выталкивание и выталкивание символа дна магазина # (в магазине этот символ один и всегда заканчивает цепочку магазинных символов).
2 Допускается выполнять вталкивание нескольких магазинных символов (Вт.АВ).
3 В ряде случаев допускается действие "заменить", т.е. верхний символ магазина заменяется некоторой указанной цепочкой (Зам. Аав) Для определенности при записи содержимого магазина будем полагать, что символ дна # занимает самое правое положение в списке. К примеру, содержимое магазина до выполнения операции " Зам. Аав " – ВВА#; после – АавВА#.
Результатом работы для МП – распознавателя будет сообщение "допустить" или "отвергнуть" цепочку, обработанную посимвольно после, поступления символа "конец цепочки" (если автомат попал в состояние ошибки, то цепочка отвергается до прихода символа "конец цепочки").
Входная цепочка допускается МП– распознавателем, если под воздействием этой цепочки автомат, начавший работу в начальной конфигурации (в начальном состоянии и с начальным содержимым магазина), находится в допускающей конфигурации после поступления символа "конец цепочки", иначе цепочка отвергается.
Пример: Построить МП –распознаватель для распознания множества цепочек следующего вида: { 0(n)1(n)| n>0} (правильная цепочка состоит из нулей, после которых следует такое же количество единиц).
Разработаем логическую последовательность действий (алгоритм работы) МП –автомата для распознания заданного по условию множества цепочек:
1 При обработке правильной цепочки первыми символами, которые нужно обработать МП –автомату, будет серия из n "0". Их количество нужно запомнить для сравнения с количеством "1".
2 Поступление каждого символа "0" будем сопровождать вталкиванием в магазин магазинного символа А для того, чтобы запомнить количество нулей и сравнить потом с количеством единиц (в начальном состоянии магазин пуст).
3 После прихода первого символа "1", нули не должны поступать (поступление "0" должно переводить автомат в состояние ошибки " Е ").
4 Поступление каждого символа "1" должно сопровождаться выталкиванием из магазина символа А. Таким образом будет контролироваться равенство количества "0" и "1".Цепочка будет допускаться МП –автоматом, если при поступлении символа"–|" магазин окажется пустым.
Реализуем описанную стратегию в конкретном МП –автомате:
1 Множество входных символов V = {0,1,–|}.
2 Множество магазинных символов {#,А}.
3 Множество состояний S = {s1, s2}.
4 Hачальная конфигурация МП –автомата – состояние s1, магазин пуст(верхний символ магазина #).
5 Допускающая конфигурация МП –автомата – состояние s2, магазин пуст(верхний символ магазина #).
6 Таблица переходов имеет вид представленный на рисунке(см. след. стр.):
 |
Проверим правильность работы построенного МП –автомата.. Для этого разберем цепочку 0011–|, которая должна быть допущена. Результаты пошагового выполнения действий сведены в таблицу.
| Необработанная цепочка | Состояние автомата | Действия с магазином | Содержимое магазина |
| 0011–| | s1 | – | # |
| 011–| | s1 | Вт. А | A# |
| 11–| | s1 | Вт. А | AA# |
| 1–| | s2 | Выт. А | A# |
| –| | s2 | Выт. А | # |
Цепочка допущена, т.к. конечная конфигурация МП –автомата допускающая (состояние s2, в магазине пусто).
5.2 Автоматы–трансляторы с магазинной памятью
В ряде случаев при обработке регулярного множества кроме распознания необходимо его преобразование в другое множество. Такие действия может выполнять МП –транслятор, на выходе которого будет формироваться выходная цепочка.
МП – транслятор задается:
1 конечным множеством входных символов (включая символ конца цепочки "–|");
2 конечным множеством выходных символов;
3 конечным множеством магазинных символов (включая маркер дна магазина – #);
4 конечным множеством состояний;
5 управляющей таблицей, которая каждой комбинации трех параметров: входной символ, магазинный символ(верхний символ магазина), состояние – ставит в соответствие четыре параметра (действие с магазином, входным символом, состоянием и выходными символами);
6 начальной конфигурацией (начальное состояние и начальное содержимое магазина);
7 множеством допускающих конфигураций (комбинаций – состояние МП –транслятора и верхний символ магазина в момент, когда приходит символ "конец цепочки").
Строение ячейки в таблице переходов МП –транслятора (см. рисунок) аналогично строению ячейки МП –распознавателя, в которую добавлено внизу четвертое поле (в нем указываются выходные символы, выдаваемые на этом шаге на выходе МП –транслятора).
 |
Ряд ячеек управляющей таблицы может без деления на поля заполняться символом Е (состояние ошибки). Если МП –транслятор попал в такое состояние, то трансляция входной цепочки прекращается и такая цепочка отвергается.
Пример: Построить МП –транслятор для распознания множества {W 2 V} и преобразования его в множество {1(n) 0(m)}, где W – произвольная цепочка из " 0 " и " 1 ", V -цепочка обратная W, m – число " 0 " до символа " 2 ", n – число " 1 " до символа " 2 " (конкретный пример цепочки и ее преобразования 0010112110100 à 111000).
