Детерминированные конечные автоматы (ДКА) и автоматные языки
Пусть ?={a1, …, am} - это алфавит, который состоит из конечного множества элементов, называемых символами (буквами).
Слово в алфавите ? - это конечная последовательность символов этого алфавита: w =w1… wn, wi
? при i=1, …, n. Число букв в этой последовательности называется
длиной слова и обозначается |w|. Имеется одно специальное "пустое" слово длины 0. Будем обозначать его через ?. На словах определена операция приписывания одного слова после другого, называемая конкатенацией: если слово w =w1… wn, а слово v =v1… vm, то их конкатенация w ? v - это слово w1… wnv1… vm длины n+m. Обычно знак конкатенации ? будем опускать и писать просто w v (по аналогии со знаком умножения в алгебре). Пустое слово - это единственное слово такое, что для любого слова w справедливо равенство w ?= ? w = w. Операция конкатенации ассоциативна: для любых трех слов w, v и u, очевидно, имеет место равенство: (w v)u = w(v u). Поэтому скобки при записи конкатенации нескольких слов будем опускать. Для представления нескольких конкатенаций одного и того же слова используют сокращенную "степенную форму" записи: w0 = ?, w1= w,…, wi+1 = wiw. Например, a3b4c2 - это сокращенная запись слова aaabbbbcc.
Языком в алфавите ? называется произвольное множество слов этого алфавита . Язык, включающий все слова в алфавите ? ( в том числе и пустое слово ?), будем обозначать через ?*.
Конечные автоматы часто используются для определения тех или иных свойств слов, т.е. для распознавания языков: автомат, распознающий некоторый язык L должен по произвольному слову w ответить на вопрос " w
L? ". Для решения такой задачи функция выходов может быть заменена на проверку того, в какое состояние переходит автомат после получения входного слова w - "принимающее" или "отвергающее".
Определение 4.3. Детерминированный конечный автомат (ДКА) - распознаватель - это система вида
включающая следующие компоненты:
- ? ={a1, … , am} (m 1) - конечное множество - входной алфавит;
- Q={q0, … , qn-1} (n 1) - конечное множество - алфавит внутренних состояний;
- q0 Q - начальное состояние автомата;
- F Q - множество принимающих (допускающих, заключительных) состояний;
- ?: Q ? ? Q - функция переходов,
- ?(q, a) - это состояние, в которое переходит автомат из состояния q, когда получает на вход символ a.
Содержание Назад Вперед