Стр. 17 - Информационные структуры и их преобразование

Содержание 15
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
Алгоритм распознавания на основе диаграммы состояний
Пусть имеем цепочку x , содержащую n терминальных символов.
Первым текущим состоянием считать начальное состояние S.
1. Начать с самого левого терминала цепочки и повторять шаг 2,
пока не будет достигнут правый её конец.
2. Сканировать следующую литеру цепочки x. Продвинуться по
дуге, помеченной этим терминалом, переходя к следующему текущему
состоянию. Если на каком-то шаге такой дуги не оказывается, то цепочка x
не является предложением языка, генерированного рассматриваемой
грамматикой. Если конец цепочки достигнут, она является предложением
тогда и только тогда, когда последнее текущее состояние есть Z(начальный
символ).
Разберём цепочку
0 1 1 0 0 1
V
Z
V
Z
Цепочка является предложением языка сгенерированного данной
грамматикой.
Если взять цепочку 111111, сразу будет ошибка.
2.2. Регулярные выражения и конечные автоматы
Все символы в языках программирования попадают в один из
следующих классов:
1) идентификаторы;
2) служебные слова;
3) целые числа;
4) операторы;
5) разделители;
6) комментарии.
Преобразуем диаграмму состояний в конечный автомат:
ДКА={ Q , Σ , δ , S , Z }
ДКА – детерминированный конечный автомат;
Q – множество состояний (алфавит нетерминальных символов);
Σ - множество входных символов (алфавит терминальных символов);