Формальные языки


Восходящие распознаватели - часть 2


/p>

 Задача распознавания принадлежности данной цепочки языку, порождаемому грамматикой Г, может быть сформулирована следующим образом. Если из заданной цепочки  с помощью операции сворачивания  можно получить начальный символ грамматики, то такая цепочка может быть построена с помощью правил заданной грамматики, и, следовательно, она принадлежит языку, порождаемому этой грамматикой.
Например, сворачивание цепочки, полученной с помощью правого вывода и правил следующей грамматики

         Г3. 11

        :
                (1) <I> ®

        a,


                (2) <I> ®

        (<I><R> ,
                (3) <R> ®

        ,<I><R> ,
                (4) <R> ®

        ).


         

      можно представить так:             (a,a) Ь 1 (<I>,a) Ь 1 (<I>,<I>) Ь 4

                  (<I>,<I><R> Ь 3(<I><R> Ь 2 <I>.

      Каждый шаг рассмотренной процедуры связан с выделением в цепочке правой части какого-либо правила и заменой его левой частью правила. В последовательности сворачиваний правые части правил  называются основой

      рассматриваемой цепочки. В общем случае основу можно определить так:
       

      Определение. Основой цепочки называют вхождение правой части последнего 
                               правила, примененного при правом выводе рассматриваемой 
                               цепочки. 

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

 

Магазин

Вход

Действие

 1. h0 (a,a)^ Перенос
 2. h0( a,a)^ Перенос
 3. h0(a ,a)^ Свертка(1)
 4. h0(<I> ,a)^ Перенос
 5. h0(<I>, a)^ Перенос
 6. h0(<I>,a )^ Свертка(1)
 7. h0(<I>,<I> )^ Перенос
 8. h0(<I>,<I>) ^ Свертка(4)
 9. h0(<I>,<I><R> ^ Свертка(3)
10. h0(<I><R> ^ Свертка(2)
11. h0<I> ^ Допустить

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

Пред.Страница 

След.Страница   Раздел   Содержание 




- Начало -  - Назад -  - Вперед -