Примеры автоматов-распознавателей
Продолжение лекции
Примеры языков.
Будем писать символы в кавычках, только если их нужно явно выделить.
1. X={a,b,c}; L={аbc, cc}. Очевидно, ссÎL, cbсÏL.
2. X={a,b,c}; L=Æ. Очевидно, ccÏL.
3. X={a,b,c}; L= X*. Очевидно, aссÎL.также как и любая цепочка из этих символов.
4. X={a,b,c}; X={anbcn| n³0}. Очевидно, aabccÎL, cbaaÏL.
5. X={a,b,c}; L={anbcm| n, m³0}. Очевидно, aaaabccÎL, cbaaÏL.
6. X={a,b,c}; L={х | в цепочке х количества вхождений а, b и с равны}. Очевидно, ссbаbаÎL, ccbÏL
7. X={0,1}; L=множество четных двоичных чисел. Очевидно, 100ÎL, 011ÏL.
8. X={(,)}; L=множество правильных скобочных выражений. Очевидно, (( ))( )ÎL, ))(( )ÏL.
9. X={+,-,0,...,9,‘.’}; L= множество вещественных констант. Очевидно, -6.7ÎL10, 23++4...6ÏL.
10. X={a}; L={aÎV* | длина a равна 2k, где k = 0, 1, ...}. Очевидно, aaaaÎL, aÏL.
11. X={a}; L={aÎV* | длина a равна 2k, где k = 0, 1, ...}. Очевидно, aaaaÎL, aÎL, aaaÏL.
12. X={большой, мощный, тяжелый, …, кран, локомотив, контейнер, …, ставит, ведет, кладет, везет,…}; L= русский язык.
Определение автомата-распознавателя
Автомат-распознаватель (или разборщик) — это специальный автомат, который позволяет определить принадлежность цепочки символов некоторому языку.
Задача распознавателя заключается в том, чтобы на основании исходной цепочки дать ответ на вопрос, принадлежит ли она заданному языку или нет.
Определение 1. Конечным автоматом-распознавателем называется пятерка объектов: А=< Q , X , Q 0 , σ , F >, где:
|
|
|
Q - конечное непустое множество (состояний);
Х - конечное непустое множество входных сигналов (входной алфавит);
Q0ÎQ - начальное состояние;
σ: Q´X®Q - функция переходов;
F - множество заключительных (финальных) состояний.
FÍQ – может включать в себя одно и более состояний, причем пустым оно не может быть.
Если автомат в процессе обработки некоторой входной цепочки 
попадает в одно из состояний из множества F 
, то это означает, что цепочка принадлежит языку.
Графически вершины, соответствующие заключительным состояниям, изображаются кружком из двойной линии или более толстой линией, а в написании будем помечать их символом +: Q+.
Автоматы-распознаватели отличаются от автоматов-преобразователей тем, что функции выходов и переходов не зависят от входных сигналов и являются одноместными функциями состояний.
Определение. Язык, для которого существует распознающий его конечный автомат, называется автоматным языком.
Очевидно, что любой конечный язык может быть задан конечным автоматом и поэтому все конечные языки - автоматные.
Но, не для всех языков существуют распознающие их конечные автоматы. Иными словами, существуют и неавтоматные языки.
|
|
|
Для представления автомата-распознавателя используется как таблицу переходов, так и граф переходов - это аналог диаграмм Мура для конечных автоматов-преобразователей.
Начинает работать автомата-распознавателя из начального состояния. Символы распознаваемой цепочки поступают посимвольно, начиная с первого изменяют состояния в соответствии с таблицей переходов.
Если найдется такая последовательность переходов из одного состояния в другое, что в результате прочтениявходного слова автомат А окажется в одном из заключительных состояний, то мы говорим, что автомат А распознает (допускает) это слово в алфавите Х. Если же такой последовательности переходов найти не удалось, слово автоматом не распознается.
Примечание:
1. В множество входных символов Х обязательно включают особый символ "конец цепочки", который сообщает КА о том, что достигнутое состояние принадлежит множеству финальных состояний F, если оно принадлежит ему то данная цепочка пропускается; в противном случае цепочка отвергается. По сути КА работает как фильтр, который пропускает "правильные" цепочки.
2. При распознании цепочек может возникнуть ситуация, когда невозможно поставить текущей паре состояние-входной символ новое состояние. Это означает, что распознаваемая цепочка не принадлежит распознаваемому множеству, хотя она и не просмотрена до символа "конец цепочки". Такие ситуации в таблице переходов помечаются символом "Е" ("error"); попав в такое состояние КА отвергает текущую цепочку и переходит в начальное состояние. В конкретных программных реализациях может вызываться обработчик ошибок, выдаваться сообщение о характере ошибки и т.п.
|
|
|
Примеры автоматов-распознавателей
Пример 1.
X={a,b,c}; L={аbc, cc}.
Полностью определенный граф переходов автомата, распознающего язык L, приведен на рисунке а). Входные цепочки “abc” и “сс” (и только они) переводят автомат из начального состояния Q 0 в одно из заключительных состояний Q 5 или Q 3.
Рисунок – Граф переходов автомата-распознавателя
Граф переходов этого же автомата-распознавателя, у которого граф переходов неполностью определен, приведен на рисунок, б).
В общем случае будем считать, что если некоторый переход Q под воздействием некоторого входного сигнала а не определен в автомате-распознавателе, то это по умолчанию означает, что существует незаключительное состояние, в которое этот автомат переходит из Q при подаче а, причем под воздействием всех входных сигналов автомат не выходит из этого незаключительного состояния.
|
|
|
В частности, в языке L нет цепочек, начинающихся с b, поэтому по сигналу bавтомат переходит в незаключительное состояние Q 6.
Далее, если автомат находится в состоянии Q 1 (после подачи сигнала a), то не могут появиться сигналы a и c, автомат переходит в незаключительное состояние Q 6. и т.д.
Пример.
В данной записи n – количество символов.
Пример.
Пример .
Пример.
Автомат распознает слова baa, abbba, bb, но не распознает слова bbb, abab, abb.
Пример.
X={a,b,c}; L={anbcn| n³0}.
Этот язык не является автоматным. На рисунке представлен один из вариантов попытки построить такой автомат, из которого видно, что автомат, фактически, должен “подсчитывать” число символов а в первой части цепочки, чтобы число символов с было в точности ему равно. Но конечный автомат имеет лишь конечную память, поэтому он не может распознавать все цепочки L. Это рассуждение, конечно, не доказательство. Дадим строгое доказательство неавтоматности L.
Теорема . Язык L={anbcn| n³0} неавтоматный.
Доказательство. Предположим противное, т. е. что существует автомат А, который распознает все цепочки языка L={anbcn| n³0} и не распознает ни одной цепочки, не принадлежащие ему. Пусть число состояний автомата А равно k. Рассмотрим цепочку аkbck. Под воздействием первой части цепочки - k последовательных символов “а” - автомат А не может не вернуться в какое-либо из состояний, в котором он уже находился. Пусть это будет состоянием Qn, и длина цикла - цепочки “аааа …а”, под воздействием которой автомат переходит из Qn в Qn, равна t, причем t>0.
Тогда цепочка аk-r так же, как и цепочка аk-rаr=аk переводят автомат А из начального состояния в состояние Qn. Но поскольку цепочка аkbck = аk-rаrbck переводит А из начального в заключительное состояние, то и цепочка аk-rbck переводит А из начального в заключительное состояние. Но поскольку r>0, то это значит, что А распознает цепочку аk-rbck, которая не принадлежит языку L={anbcn| n³0}. Итак, мы пришли к противоречию, предположив существование конечного автомата, распознающего L.
Пример.
X={a,b,c}; L={anbcm| n, m³0}.
В отличие от предыдущего языка, L – автоматный. Автомат рисунке только с двумя состояниями распознает L. Простота этого распознавателя объясняется тем, что он не должен отслеживать количества символов а и с во входных цепочках.
Рисунок
Пример.
X={a,b,c}; L={х | в цепочке х количества вхождений а, b и с равны}.
L не автоматный.
Пример.
X={0,1};
L=множество четных двоичных чисел. Автомат рисунке с двумя состояниями распознает L.
Рисунок
Пример.
X={+,-,0,...,9}; L=множество целых констант.
Автомат с тремя состояниями распознает L. Вместо конечного числа цифр на переходах здесь поставлена просто буква ц, обозначающая любую цифру.
Пример.
X={ (, ) }; L=множество правильных скобочных выражений.
L9 не автоматный. Распознавание вложенных скобок требует запоминания произвольных объемов информации: глубина вложенности может быть любой.
Пример.
X={+,-,0,...,9,’.’}; L= множество вещественных констант.
Автомат распознает L. Заметьте, что автомат правильно распознает константы, в которых можно не писать знак и либо целая, либо дробная часть может быть опущена, но не обе сразу. Десятичная точка как признак вещественного числа обязательна.
Дата добавления: 2020-11-29; просмотров: 1337; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!