66 (Вопросы по разным темам с ответами (программирование))

66 Распознаватели и преобразователи: конечные автоматы и преобразователи, автоматы и преобразователи с магазинной памятью

Распознавателем языка называется программа, которая получает на вход строку х и отвечает "да", если х— предложение языка, или в противном случае "нет". Мы компилируем регулярное выражение в распознаватель путем построения обобщен­ной диаграммы переходов, называемой конечным автоматом. Такой автомат может быть детерминированным или недетерминированным (недетерминированный автомат может иметь более одного перехода из состояния при одном и том же входном символе).

Как детерминированные, так и недетерминированные конечные автоматы способны к распознаванию точных регулярных множеств. Таким образом, они могут распознавать все, что могут обозначать регулярные выражения. Однако детерминированные конечные автоматы, которые приводят к более быстрому распознаванию, обычно больше по раз­меру, чем эквивалентные недетерминированные. В следующем разделе будут рассмотре­ны методы преобразования регулярных выражений в оба типа конечных автоматов. Пре­образование в недетерминированный автомат более очевидно, поэтому вначале обсудим именно этот тип автоматов.

Недетерминированные конечные автоматы

Недетерминированный конечный автомат представляет собой математическую модель, состоящую из

■ множества состояний S;

■ множества входных символов Σ {символов входного алфавита);

■ функции переходов тоvе, которая отображает пары символ-состояние на множество состояний;

■ состояния S₀, известного как стартовое {начальное);

■ множества состояний F, известных как допускающие {конечные);

НКА может использоваться в виде помеченного ориентированного графа, так назы­ваемого графа переходов, узлы которого представляют собой состояния, а помеченные дуги составляют функцию переходов. Такой граф похож на диаграмму переходов, одна­ко один и тот же символ может помечать два и более переходов из одного состояния, а некоторые переходы могут быть помечены специальным символом е, как обычным входным символом (е-переходы).

Детерминированный конечный автомат

Детерминированный конечный автомат явля­ется специальным случаем недетерминированного конечного автомата, в котором

■ отсутствуют состояния, имеющие е-переходы;

■ для каждого состояния S и входного символа а существует не более одной дуги, исхо­дящей из S и помеченной как а.

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

Организация автомата с магазинной памятью

Автомат с магазинной памятью (сокращенно МП-автомат) - это семерка P=(Q,T,Г,d,q₀,Z₀,F), где

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

2. T - конечный входной алфавит;

3. Г - конечный алфавит магазинных символов;

4. d - функция переходов - отображение множества Q ×(T {e}) × Г в множество конечных подмножеств Q×Г*, т.е. d:Q×(T {e})×Г -> {Q×Г*};

5. q₀<-Q - начальное состояние управляющего устройства;

6. Z₀<-Г - символ, находящийся в магазине в начальный момент (начальный символ);

7. F<=Q - множество заключительных состояний

Конфигурацией МП-автомата называется тройка (q,w,u)<-Q×T*×Г*, где

1. q - текущее состояние управляющего устройства;

2. w - неиспользованная часть входной цепочки; первый символ цепочки w находится под входной головкой; если w= e, то считается, что вся входная лента прочитана;

3. u - содержимое магазина; самый левый символ цепочки u считается верхним символом магазина; если u=e, то магазин считается пустым.

Такт работы МП-автомата P будем представлять в виде бинарного отношения |-, определенного на конфигурациях. Будем писать

(q,aw,Zu)|-(q',w,vu)

если множество d(q,a,Z) содержит (q',v), где q, q'<-Q, a<-T {e}, w&lt;-T*, Z<-Г, u,v<-Г*.

Начальной конфигурацией МП-автомата P называется конфигурация вида (q₀,w,Z₀), где w<-T*, т.е. управляющее устройство находится в начальном состоянии, входная лента содержит цепочку, которую нужно распознать, а в магазине есть только начальный символ Z₀. Заключительная конфигурация - это конфигурация вида (q,e,u), где q<-F, u<-Г*.

Говорят, что цепочка w допускается МП-автоматом P, если (q0,w,Z0)|-*(q,e,u) для некоторых q<-F и u<-Г*. Языком, определяемым (или допускаемым) автоматом P (обозначается L(P)), называют множество цепочек, допускаемых автоматом P.

Иногда допустимость определяют несколько иначе: цепочка w допускается МП-автоматом P, если (q₀,w,Z₀) |-*(q,e,e). Эти определения эквивалентны.