Автоматные языки

Общая теория конечных автоматов сводится к анализу и синтезу автоматов. Анализ: по и изучить особенности внешнего поведения автомата. Синтез: по внешнему поведению построить функции и . Вторая задача значительно сложнее первой.

Частные случаи практически важных КА (конечных автоматов):

– сумматор;

– задержка (автомат задержки – это автомат Мура);

– счетчик.

Автоматы подразделяются на преобразователи и распознаватели. Иногда вместо распознавателя употребляется термин «акцептор». Все предыдущие автоматы являлись преобразователями. В настоящее время одно из основных применений автомата – установление факта принадлежности подстроки данной строке.

Рассмотрим задачу: установить наличие в заданной строке слова «резец». Синтез соответствующего автомата начинается с построения графа (рис. 4.6).

Рис. 4.6. Граф распознавания заданного слова

По графу строим таблицу, описывающую работу автомата-распознавателя:

р	/0	н/0	н/0	н/0	н/0
е	н/0	/0	н/0	/0	н/0
з	н/0	н/0	/0	н/0	н/0
ц	н/0	н/0	н/0	н/0	н/1
S	н/0	н/0	н/0	н/0	н/0

Далее подаем некоторую строку. Подстрока считается выявленной, если на выходе появляется единица:

а

с

б

л

к

р

р

е

з

а

р

е

з

е

ц

у

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

Полученные таблицы для реализации функции допускают сжатие путем составления массива номеров строк и столбцов, отличных от н/0. Количество операций имеет порядок длины слова при автоматном распознавании.

В качестве задания осуществить проверку наличия какого-нибудь слова (или предложения) в произвольно выбранном тексте. Например, рассмотреть исходный текст некоторой программы на алгоритмическом языке PASCAL и проверить наличие выражения «for I:=» в этом тексте.

Основной технический аппарат при изучении автоматных языков – акцепторы, автоматы-распознаватели. Распознаватели осуществляют выделение всех входных предложений, принадлежащих языку. Автоматные языки – очень узкий класс всех возможных языков.

Словарь – это конечное множество.

Элементы словаря – символы (буквы).

Предложение – все конечные последовательности символов из заданного словаря.

– множество всех цепочек, построенных по данному словарю.

Множество содержит бесконечное количество элементов.

Грамматика – конечный механизм задания языка.

Существует два вида грамматик – порождающая и распознающая: первая – это механизм, позволяющий строить все допустимые предложения, вторая – отсеивает из множества те предложения, которые не принадлежат языку.

Синтаксис – правила построения языка.

Дата добавления: 2015-06-04