Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
ОПРЕДЕЛЕНИЕ. Множество U A*распознается автоматом Â из начального состояния q0и множества D Q- распознающих состояний
|
|
Множество 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 называется автоматным языком.