Детерминированные конечные автоматы (ДКА) и автоматные языки

Пусть ?={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.

Содержание Назад Вперед