yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->3.2 Построение КА-распознавателей для праволинейных грамматик

Дискретная математика

3.2 Построение КА-распознавателей для праволинейных грамматик

     Праволинейной называется контекстно-свободная грамматика,  вправых частях правил которой имеется не более одного  нетерминала и этот нетерминал заканчивает правило.  В праволинейных грамматиках допускаются эпсилон-правила вида  X  ->  @  (т.е.  нетерминал преобразуется в пустую цепочку).

     Праволинейную грамматику всегда можно преобразовать в  автоматную, для которой построение  КА-распознавателя  рассмотрено  в предыдущем разделе. Алгоритм преобразования правил следующий:  а) преобразовать правила вида A -> xyzB, где xyz - цепочка терминалов произвольной длины (в данном случае ¦ xyz ¦ = 3 ); вводят дополнительные нетерминалы по следующему принципу:

  A -> x<yzB>; <yzB> -> y<zB>; <zB> -> zB (в угловых скобках  записаны цепочки, для обозначения которых вводят  новые  нетерминалы);

  Таким образом происходит замена исходного правила  несколькими, которые сответствуют правилам автоматной грамматики. В нашем случае:

                               ¦   A -> xM

       A -> xyzB   ==========> ¦   M -> yN

                               ¦   N => zB

  б) преобразовть правила  вида A -> xyz, где  xyz - цепочка терминалов произвольной длины (в данном случае ¦ xyz ¦ = 3 ); вводят дополнительный нетерминал F, который в КА будет служить  финишным состоянием (см. разд. 3.1), а в преобразованной грамматике  добавить правило  F -> @

                        ¦ A -> xyzF ===>  ¦  см. пункт а)

       A -> xyz  ====>  ¦

                        ¦ F -> @

 

     В результате таких преобразований получим автоматную грамматику, эквивалентную исходной праволинейной, для  которой  КА-распознаватель строится, как описано в разделе 3.1.

     Примечания

  1.При построении таблицы переходов в последнем столбце  ставить

"доп." для всех состояний КА, для которых в полученной грамматике

есть эпсилон-правила.

  2.Полученный КА обязательно проверить на достижимость и эквивалентность состояний; при необходимости выполнить процедуру преобразования в минимальный КА (переименование состояний КА не  изменит множества распознаваемых цепочек).

 

        8.3 Построение МП-распознавателей для S-грамматик

 

     КС-грамматика (грамматика второго типа) называется S-грамматикой, если правые части всех правил этой грамматики начинаются стерминальных символов и для правил с одинаковыми  левыми  частями правые части начинаются с различных терминалов.

     Правила имеют вид Х -> y&, где y - терминал; & -  любая  цепочка терминалов и нетерминалов, возможно пустая (S-грамматика несодержит эпсилон-правил).

     Для S-грамматики существует формальная процедура  построения МП-распознавателя с одним состоянием  S по следующему алгоритму:

  1.Входной алфавит МП-распознавателя  V = {VT,-+}.

  2.Множество магазинных символов {  VN,  VT1,  \/},  где  VT1  -часть терминальных символов грамматики, которые встречаются в цепочках & множества правил.

  3.Начальная конфигурация - в магазине находится начальный  символ грамматики (например для грамматики G[Z] -  Z \/).

   Замечание: условимся запись содержимого  магазина  вести  так, чтобы верхний символ (тот, с которым работает МП-автомат) занимал самую левую позицию.

  4.Управляющая таблица строится так: столбцы таблицы  -  символы входного алфавита (последний символ -+);строки таблицы - магазинные символы.

 

 

 

 

 

 

 

 

 

Заполнение управляющей таблицы:

   а) для правил грамматики вида Х -> y& (& не пустая цепочка)

           .... ¦   y    ¦

                ¦        ¦  ....

               ............

           -----+--------+----------

                ¦\Зам.& /¦

            X   ¦ \    / ¦  ....

                ¦S \  / П¦

           -----+---\/---+----------

               ............

           .... ¦ .....  ¦  ....

 

   б) для правил грамматики вида  Х -> y (&  пустая цепочка)

           .... ¦   y    ¦

                ¦        ¦  ....

              ..............

           -----+--------+----------

                ¦\Выт.Х /¦

            X   ¦ \    / ¦  ....

                ¦S \  / П¦

           -----+---\/---+----------

               ............

           .... ¦ .....  ¦  ....

   В соответствии с п.п. а) и б) обрабатывается все  множество  Р правил грамматики.

   в) клетки таблицы на пересечении терминал-магазинный символ  и тот же терминал-входной алфавит:

           ....  ¦   y    ¦

                 ¦        ¦  ....

                .............

           ------+--------+----------

                 ¦\Выт.y /¦

            y    ¦ \    / ¦  ....

                 ¦S \  / П¦

           ------+---\/---+----------

                .............

           ....  ¦ .....  ¦  ....

   г) все клетки последнего столбца таблицы (-+)  заполняются "отв." кроме клетки на пересечении со строкой  \/,  в  которой  ставится"доп."

   д) оставшиеся клетки заполняются буквой Е-"состояние ошибки".

 

     Пример  Задана грамматика G[S] =(VT={a,b};VN={S,R}; S; P);

             P={S->abR (1); S->bRbS (2); R->a (3); R->bR (4)}.

     Построить МП-распознаватель  для  языка,  порождаемого  этой грамматикой.

 

                       Решение

 

  1.Проверка нетерминалов на достижимость и продуктивность

 S достижим (начальный символ); R достижим (правило 1);

 R продуктивен (правило 3); S продуктивен (правило 1).

 

  2.Построение МП-распознаватель(по виду правил делаем  заключение, что это S-грамматика):

 

    - входной алфавит V={a,b,--+};

 

    - множество магазинных символов {S,R,b,\/};

 

    - начальное содержимое магазина  S,\/;

 

    - управляющая таблица имеет вид:

 

             г======T========T========T=======¬

             ¦      ¦    a   ¦    b   ¦  -+   ¦

             ¦      ¦        ¦        ¦       ¦

             ¦------+--------+--------+-------¦

             ¦  \/  ¦   E    ¦    E   ¦ доп.  ¦

             ¦      ¦        ¦        ¦       ¦

             ¦------+--------+--------+-------¦

             ¦      ¦\ Зам. /¦\ Зам. /¦       ¦

             ¦  S   ¦ \ bR / ¦ \RbS / ¦ отв.  ¦

             ¦      ¦  \  / П¦  \  / П¦       ¦

             ¦------+---\/---+---\/---+-------¦

             ¦      ¦\ Выт. /¦\ Зам. /¦       ¦

             ¦  R   ¦ \ R  / ¦ \ R  / ¦ отв.  ¦

             ¦      ¦  \  / П¦  \  / П¦       ¦

             ¦------+---\/---+---\/---+-------¦

             ¦      ¦        ¦\ Выт. /¦       ¦

             ¦  b   ¦   E    ¦ \ b  / ¦ отв.  ¦

             ¦      ¦        ¦  \  / П¦       ¦

             L======¦========¦===\/===¦=======-

     Примечание: поле для состояний осталось незаполненным,  т.к.заполнять его нет смысла (состояние только одно).

  3.Проверка работы МП-распознавателя.

    Получим контрольную цепочку на основании правил грамматики:

     2       1         4          3          3

   S -> bRbS -> bRbabR -> bRbabbR -> bRbabba -> bababba

 

    Работу МП-распознавателя по разбору цепочки bababba  предста-

вим в виде таблицы:

  -------------T-----------T-----------T------------T------------¬

  ¦  Необработ.¦ Обраб. вх.¦Верхн.симв.¦Содержимое  ¦  Действие  ¦

  ¦  цепочка   ¦ символ    ¦магазина   ¦магазина    ¦  с магаз.  ¦

  +---------T--+-----------+-----------+------------+------------+

  ¦ bababba-+  ¦     b     ¦     S     ¦   S \/     ¦  Зам. RbS  ¦

  ¦  ababba-+  ¦     a     ¦     R     ¦   RbS\/    ¦  Выт. R    ¦

  ¦   babba-+  ¦     b     ¦     b     ¦   bS\/     ¦  Выт. b    ¦

  ¦    abba-+  ¦     a     ¦     S     ¦   S\/      ¦  Зам. bR   ¦

  ¦     bba-+  ¦     b     ¦     b     ¦   bR\/     ¦  Выт. b    ¦

  ¦      ba-+  ¦     b     ¦     R     ¦   R\/      ¦  Зам. R    ¦

  ¦       a-+  ¦     a     ¦     R     ¦   R\/      ¦  Выт. R    ¦

  ¦        -+  ¦     -+    ¦    \/     ¦    \/      ¦  допустить ¦

  L------------+-----------+-----------+------------+-------------

                           - 28 -

     Контрольная цепочка распознается построенным  МП-распознавателем.

     Работу МП-распознавателя можно трактовать так: на каждом шаге процесса обработки цепочки магазин представляет следующее  утверждение о цепочке необработанных символов (включая и текущий) "вся цепочка будет допущена тогда и только  тогда,  когда  оставшаяся необработанной цепочка входных символов выводима из цепочки

символов, находящихся в магазине".

 

 

42