Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Автоматы-распознаватели
|
|
Пусть задана некоторая порождающая грамматика G, и задано слово a в ее терминальном алфавите.
Спрашивается: принадлежит ли слово aязыку, порождаемому грамматикой G?
Эту задачу называют проблемой принадлежности для грамматики G.
Решение проблемы принадлежности состоит в разработке распознающего алгоритма, который для произвольной грамматики G и слова a за конечное число шагов выдает ответ на поставленный выше вопрос.
Такие алгоритмы (представляющие собой абстрактные математические модели некоторого вычислительного устройства) традиционно называют автоматами-распознавателями.
Наиболее просто устроены распознаватели регулярных языков – конечные автоматы.
Конечный автомат - распознаватель это объект вида M = á T, Q, s 0, D, F ñ, состоящий из пяти следующих компонент:
1. T = { a 1, …, am } (m ³ 1) – конечное множество, представляющее собой входной алфавит автомата.
На вход автомата для анализа поступает последовательность символов (входное слово) в алфавите T.
Автомат «считывает» эту последовательность, двигаясь в постоянном направлении (возвращение к прочитанному ранее символу невозможно). За один свой «такт» автомат рассматривает только один текущий символ, повторяя «такты» до тех пор, пока слово не закончится (может, например, стоять специальный маркер конца).
2. Q ={ s 0, …, sn -1} (n ³ 1) - конечное множество состояний, в которых может находиться автомат (точнее, его управляющее устройство) в момент «считывания» очередного символа (это тоже некий алфавит);
3. s 0 – выделенное начальное состояние автомата, s 0 Î Q. В этом состоянии автомат находится, когда поступает для анализа новое входное слово.
4. D - множество заключительных или допускающих состояний автомата, D Í Q.
Язык L распознаваемый (допускаемый) конечным автоматом M, состоит из всех допускаемых данным автоматом слов. Обозначается такой язык L (М).
5. F – функция перехода или система команд автомата. 
.
Входом для F является буква из Т (например, а) и состояние (s) из Q.
Выходом – состояние из Q 
.
Предположим, что алфавит 
, автомат М читает слово aba, 
, а функция перехода задана таблицей:
Тогда 
, При этом a – метка перехода из s0 в s1.
, 
.
Удобный способ описания конечного автомата (КА)
Диаграмма состояний представляет собой размеченный орграф, вершины которого — состояния КА, дуги — переходы из одного состояния в другое, а разметка дуг — метки перехода из алфавита T.
Начальное состояние распознается по ведущей в него короткой стрелке: 
Приведенный автомат графически:
Если найдется такая последовательность переходов из одного состояния в другое, что в результате прочтения входного слова автомат М окажется в одном из заключительных состояний, то мы говорим, что автомат М распознает (допускает) это слово в алфавите T.
Если же такой последовательности переходов найти не удалось, слово автоматом не распознается.
Каждое допускающее состояние отмечается на диаграмме двойным кружком: 
.
Пример.
Автомат допускает (распознает) слова baa, abbba, bb,
но не распознает слова bbb, abab, abb.
Пример.
Автомат допускает (распознает) слова:
bb, aababaaa, baaab, babaaa, aabaabaa, …
Автомат может прочесть любое слово языка, заданное регулярным выражением
a*ba*ba*.
Или такой язык можно описать как множество всех слов, содержащих точно два b.
Состояние s 4 является примером состояния зацикливания.
Если в конечном автомате имеются несколько переходов с общим началом и общим концом, то такие переходы называются параллельными.
Пример.
Параллельные переходы можно изображать одной стрелкой. При этом метки переходов перечисляют через запятую.
Упрощенный вид:
Автомат допускает (распознает) только слова ab, ac. Этот язык можно задать с помощью регулярного выражения
.
Пример.
Каждое слово следует начинать с ab и заканчивать на c.
Однако, учитываю петлю aabc, которая начитается и заканчивается в s4, получаем регулярное выражение для аватомата 
.
Пример
Так как при чтении трех последовательных b автомат переходит в s 3, а все остальные – финальные состояния, то язык, который допускает автомат, состоит из всех слов, не включающих три последовательных b.
Рассмотренные автоматы являются детерминированными автоматами.
Детерминированный конечный автомат –автомат, из одного состояния которого не может выходить несколько переходов (стрелок), помеченных одним и тем же символом.
Детерминированный конечный автомат любую данную последовательность входных символов переводит из текущего состояния в следующее единственно возможным способом. Соответственно, после прочтения слова можно сразу сказать, допустимо оно или нет.
Пример 1. Конечный автомат, его входной алфавит T ={ a, b }.
Представленный конечный автомат является недетерминированным, поскольку допускает, что из одного состояния может выходить несколько переходов (стрелок орграфа), помеченных одним и тем же символом.
В этом случае F не функция, а правило перехода.
Определение. Детерминированный конечный автомат называется полным, если из каждого его состояния по каждому входному символу возможен переход в некоторое состояние.
Пример: Конечный автомат: детерминированный, но не полный.
Автомат допускает язык, задаваемый регулярным выражением 
.
Пример.
Автомат допускает язык, задаваемый регулярным выражением 
.
Теорема. Языкдопускается конечным автоматом тогда и только тогда, когда он порождается регулярной грамматикой.
Теорема. Любой недетерминированный конечный автомат может быть преобразован в эквивалентный ему полный детерминированный конечный автомат.
Эта теорема доказывается конструктивным образом, т.е. путем указания общего алгоритма построения детерминированного автомата, определяющего тот же язык, что и исходный недетерминированный.
|
|