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

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

                           Тема № 8  Построение распознавателей для грамматик

План

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

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

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

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

8.5 Задачи  преобразование  грамматик  и построение МП-распознавателей  ................................    

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

 

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

 

     Любое регулярное множество, которое распознается  КА,  можно описать с  помощью  автоматной  грамматики.  Алгоритм  построения грамматики следующий:

     1.Начальный символ грамматики - начальное состояние КА.

     2.Терминальные символи грамматики - алфавит КА (без  символа

"конец цепочки" --+).

     3.Нетерминальные символы грамматики - множество состояний КА.

     4.Если в таблице переходов КА есть переход из состояния А  в состояние В при поступлении входного символа х -  ввести  правило следующего вида:  А -> xB .

     5.Если D - допускающее состояние КА, то ввести правило  следующего вида: D -> @ (@-пустая цепочка).

     Пример  Задан КА                            a  b   -+

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

     - множество состояний S={A,B,C};          ¦       ¦

     - начальное состояние A;                B ¦ A  C  ¦ отв

     - множество допускающих состояний         ¦       ¦

       S1={A,C}.                             C ¦ C  B  ¦ доп

                                               L--------

     Построить грамматику, языком которой будет  множество  цепочек, допускаемых заданным КА.

 

                         Решение

1. Начальный символ грамматики A.

2. Множество терминальных символов грамматики VT={a,b}.

3. Множество нетерминальных символов VN={A,B,C}.

4. Множество правил P ={ A -> aA (1);   A -> bB (2); B -> aA (3);

B -> bC (4); C -> aC (5); C -> bB (6); A -> @ (7);  C  ->  @(8)}.

     Для проверки правильности построения грамматики получим  вывод цепочки  aaabb, которая допускается заданным КА.

      (1)    (1)     (1)      (2)       (4)        (8)  (правила)

     A --> aA --> aaA --> aaaA --> aaabB --> aaabbC --> aaabb

 

     Для всякой автоматной грамматики (грамматика  типа  3)  можно построить КА-распознаватель.  Алгоритм построения КА - распознавателя следующий:

     1.Входной алфавит КА  V = {VT,-+ }.

     2.Множество состояний КА S =  {VN,F}  (F-финишное  состояние КА - единственное допускающее состояние КА-распознавателя).

     3.Начальное состояние КА - начальный символ грамматики.

     4.Множество допускающих состояний  S1 = { F }.

     5.Таблица переходов КА (управляющая таблица)  строится  следующим образом:

     - обозначить столбцы таблицы символами входного алфавита  КА

(последний столбец - символ "конец цепочки");

     - обозначить строки таблицы  состояниями  КА  (первая  строка-начальное состояние КА);

     - в соответстви с правилами X -> yZ заполнить клетку таблицы на пересечении строки Х и столбца y  переходом в состояние Z;

     - в соответствии с правилами Х -> z заполнить клетку таблицы на пересечении строки Х и столбца z переходом в состояние F;

     - заполнить клетки последнего столбца (все "отв.", кроме пересечения F и -+ - "доп.");

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

 

     Примечания:

 

  1.Перед началом  построения  КА-распознавателя  проверить  множество нетерминалов грамматики G  на  продуктивность  и  достижимость; при необходимости выполнить  эквивалентные  преобразования грамматики G в G1 с укороченым множеством правил Р.

 

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

преобразовать в КА-распознаватель.

 

    Пример

    Для грамматики  G[Z] построить КА-распознаватель.

G[Z] = (VT={a,b,c}; VN={ Z,A,B  };  Z;  P={Z->aA,  A->bA,  A->cB, B->cZ,

B->b, A->a}).

                        Решение

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

 а) продуктивны нетерминалы A и В (на  основании  двух  последних правил); на основании первого правила продуктивен нетерминал Z;

 б) достижими все терминалы (правила 1 и 3).

 

  2.Зададим параметры автомата-распознавателя:

 

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

    - множество состояний автомата S={Z,A,B,F};

    - начальное состояние автомата - Z;

    - множество допускающих состояний автомата S1={ F };

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

 

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

              ¦       ¦  a  ¦   b  ¦   c  ¦  -+  ¦

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

              ¦    Z  ¦  A  ¦   E  ¦   E  ¦ отв. ¦

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

              ¦    A  ¦  F  ¦   A  ¦   B  ¦ отв. ¦

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

              ¦    B  ¦  E  ¦   F  ¦   Z  ¦ отв. ¦

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

              ¦    F  ¦  E  ¦   E  ¦   E  ¦ доп. ¦

              L=======¦=====¦======¦======¦======-

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

 на эквивалентность состояний и минимизировать  (проверить  самостоятельно).

     Проверка работы КА: Пусть задана цепочка из грамматики  G[Z] abccaa (вывод в грамматике получить самостоятельно).

 

 

         Необработанная    Текущее состояние   Новое состояние

             цепочка         КА - расп-ля        КА - расп-ля

           abccaa-+                Z                   A

            bccaa-+                A                   A

             ccaa-+                A                   B

              caa-+                B                   Z

               aa-+                Z                   A

                a-+                A                   F

                 -+                F                  доп.

 

     Примечание: по самому левому символу необработанной цепоки и текущему состоянию КА в соответствии с таблицей переходов вырабатывается новое состояние.

     Заданная цепочка будет допущена построенным КА-распознавателем.

 

41