Идентификация слов: метод автомата

Рассмотрим построение конечного автомата (процессора), который по представленному входному слову с концевым маркером устанавливает его идентичность некоторому элементу множества.

Пример:

Возможная организация лексического блока

Управляющая программа знает, что некоторая цепочка букв, появившаяся в некотором месте программы, должна быть словом, и подает эти буквы на вход идентифицирующего конечного автомата для анализа. Когда управляющий автомат обнаруживает, что слово кончилось, он посылает на вход идентифицирующего автомата концевой маркер. Предполагаем, что буквы уже переведены в символьные лексемы типа (БУКВА, значение). Под действием входного символа буква управляющий автомат передает значение этой буквы на вход идентифицирующего автомата и сам совершает определенный переход. Если идентифицирующий автомат использовать таким образом, то язык должен быть таким, чтобы управляющий автомат узнавал какие входные символы, следуя друг за другом, образуют слово.

Автомат, идентифицирующий некоторое множество слов может быть построен путем введения в него состояния для любой подцепочки, которая может быть префиксом какого-либо слова из этого множества. Множество префиксов включает в себя пустую цепочку, которая служит префиксом для всех слов, а также сами заданные слова.

Пример:

Построить конечный процессор, имеющий входной алфавит {О, Б, С, К, А, ð} для идентификации множества {ОСА, БОК, БОКА, БАК}.

Элементы таблицы в кавычках означают, что автомат идентифицировал соответствующее слово. Пустые ячейки соответствуют выходам «слово Ï множеству». Сообщение об ошибке откладывается, пока слово не просмотрено полностью. Переходы не сопровождаются никакими действиями, кроме изменения состояния.

Вопросы и упражнения

Построить конечный процессор, имеющий входной алфавит {О, М, С, Ы, И, А, ð} для идентификации множества {САМ, СОМ, САМИ, СОМЫ, МЫС}.