|
Пусть Á = (A, B, Q, j, y) - некоторый автомат и q 0 - начальное состояние Á, а D Í Q -множество состояний, называемых распознающими состояниями.
Тогда автомат Á распознает входное слово , если после переработки из состояния q 0он оказывается в состоянии из множества D. Способность конечных автоматов распознавать слова из заданных множеств слов делает возможным применение автоматов в качестве устройств, проверяющих правильность входных слов автоматов.
ОПРЕДЕЛЕНИЕ
Множество U A *распознается автоматом Â из начального состояния q 0и множества D Q - распознающих состояний, если
" Î A *( Î U Â распознает ).
Например. Если A = { o, s }, то множество слов в этом алфавите, имеющих вид: 1 sos 2, где 1 и 2 - это произвольные слова из A *, распознается автоматом, изображенным на рис. 7.10. В приведенной на этом рисунке диаграмме не отображены сведения о значениях вункции выхода автомата, поскольку они не влияют на процесс распознавания
о
q 0
s o s, o
s q 1 q 3
o q 2 s
Рис. 7.10
Здесь q 0 - начальное состояние автомата, а { q 3} - множество распознающих состояний.
Состояние q 0 соответствует ситуации, когда поступившая на вход автомата часть перерабатываемого слова не заканчивается никаким началом слова вида sos 2.
Тогда состояние q 1 соответствует ситуации, когда последний поступивший на вход символ может быть первым в слове sos, q 2 соответствует случаю, когда два последних символа это so. Наконец, q 3 соответствует случаю, когда на входе автомата уже появились последовательно все символы слова sos.
Заметим, что для распознавания слов конечными автоматами значения символов на выходе автомата несущественны.
Поэтому в диаграмме из приведенного примера дуги не размечены значениями выходных символов.
В дальнейшем автомат Â = (A, B, Q, j, y), который распознает множество слов U из начального состояния q 0 для множества распознающих состояний D, будем записывать как Â = (A, Q, j, q 0, D).
Если некоторое множество U A *распознается некоторым конечным автоматом, то U называется автоматным языком.
ТЕОРЕМА 7.6
Множество автоматных языков замкнуто относительно операций объединения, пересечения, разности и дополнения языков.
Дата добавления: 2015-11-30; просмотров: 27 | Нарушение авторских прав