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


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


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

Определение. Пусть задана грамматика Г, в схеме которой имеется    правило 
                         r =A®y  и задана цепочка  g = r1A r2.  Если правая часть цепочки 
                         правила r является частью цепочки , то можно получить цепочку 
                         t = r1y r2 , заменяя правую часть правила грамматики левой частью. 
                         В этом случае говорят, что цепочка  tt   получается путем 
                         непосредственного сворачивания цепочки g  и   используют 
                         обозначение 
                                             t <= g
Определение. Если существует множество цепочек    W  = ( w1, w2, ...wn  ),  
                          таких, что     w1 Ь   w2 ,    w2 Ь    w3 ,  ...  ,  wn-1Ь   wn , 
                           то говорят, что цепочка  wn    сворачивается в цепочку  w1   и 
                           используют обозначение 
                                                     w1 *Ь   wn . 
 
<


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