Механизмы распознавания и преобразования

Разработка и применение языков обычно требуют проработки по крайней мере двух основных проблем:

1. должен быть создан механизм порождения языка, т.е. система описания строк языка

2. решена задача проверки принадлежности заданной строки заданному языку

Для решения второй проблемы создается механизм распознавания или распознаватель.

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

Входная лента

Входная головка

Распознаватель выполняет некоторую последовательность шагов, каждый из которых включает:

§ чтение текущего символа входной ленты;

§ анализ входного символа, содержимого памяти и текущего состояния;

§ перемещение (если нужно) входной головки;

§ изменение содержимого памяти;

§ изменение состояния распознавателя.

Поведение распознавателя можно проследить по его конфигурациям. Конфигурация – это как бы мгновенный снимок распознавателя, на котором зафиксированы:

§ состояние управляющего устройства;

§ содержимое входной ленты и положение входной головки;

§ содержимое вспомогательной памяти.

Управляющее устройство называется детерминированным, если для каждой конфигурации распознавателя существуют не более одного возможного следующего шага. Недетерминированное управляющее устройство для каждой конфигурации имеет конечное множество возможных следующих шагов.

Для каждого класса грамматик из иерархии Хомского существует класс распознавателей, определяющих тот же класс языков.

Распознаватели для языков класса 3 называют конечными автоматами, для языков класса 2 – автоматами с магазинной памятью, для языков класса 1 – линейными ограниченными автоматами (машинами Тьюринга с конечным объемом ленты), для языков класса 0 – машинами Тьюринга.

Дата добавления: 2014-01-03