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

---

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

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

Определение. Пусть задана грамматика Г, в схеме которой имеется    правило 
                         r =A®y и задана цепочка  g = r₁A r₂. Если правая часть цепочки 
                         правила r является частью цепочки , то можно получить цепочку 
t = r₁y r₂ , заменяя правую часть правила грамматики левой частью. 
                         В этом случае говорят, что цепочка  tt   получается путем 
                         непосредственного сворачивания цепочки g  и   используют 
                         обозначение 
t <= g .
Определение. Если существует множество цепочек   W  = ( w₁, w₂, ...w_n ),
                          таких, что  w₁ Ü w₂ , w₂ Ü w₃ , ... , w_n-1Ü w_n , 
                           то говорят, что цепочка  w_n    сворачивается в цепочку  w₁   и 
                           используют обозначение 
w₁ *Ü w_n .

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

Г_{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>	^	Допустить

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

Расширенный магазинный автомат

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

 Определение. 
                         Формальное определение такого автомата имеет вид: 

    M = {P, S, H, F, s0, h0, d},

 где  
    P - входной алфавит, 
    S - алфавит состояний, 
s₀- начальное состояние , s₀ ÎS,
    F - множество конечных состояний, F является подмножеством S, 
    H - алфавит магазинных сисмволов, записываемых на вспомогательную ленту, 
    h₀ - маркер дна, он всегда записывается на дно магазина, h₀ Π H, 
d: S * {P È {$}} * H* ® S*H* - функция переходов. 

В функциональном виде функции переходов расширенного автомата можно записать так:

 d(s, p, ga) = (s, gb),

где a, b, g Î H*, p Î (P È {$}) и s Î S.
Приведенное определение показывает, что расширенный автомат допускает замену одной цепочки, находящейся в вершине автомата, другой цепочкой.
Используя введенное  ранее определение конфигурации  автомата, работу расширенного  магазинного автомата можно представить в виде последовательности сменяющих друг друга конфигураций. При этом начальная и конечная конфигурации имеют вид:

(s₀, a, h₀ ) и (s₁, $, h₀I ),

где  a - заданная цепочка, s₁ - одно из заключительных состояний автомата, I - начальная аксиома грамматики.
Цепочку и язык, допускаемые расширенным автоматом, можно определить так.

Определение. 
                     Цепочка допускается расширенным автоматом, если
                     существует  последовательность конфигураций, 
                      первая из которых является начальной конфигурацией 
                       с заданной цепочкой, а последней  конфигурацией в 
                        последовательности является одна из 
                         заключительных конфигураций. 

( s₀, a, h₀ )  , $|--*  ( s₁, h₀I ),

    где s₁ - одно из заключительных состояний,  
a - заданная  цепочка.

Определение. 
                     Язык, допускаемый расширенным автоматом, можно 
                      определить  так: 

L(M) = { a | (s₀, a, h₀ )  |--*  ( s₁, $,$ ) и  s₁ÎF}. 

Пример работы расширенного магазинный автомат

В качестве иллюстрации работы расширенного автомата рассмотрим автомат, допускающий язык L={ww^R | w Î {a, b}*}.

M_3.2:    P = {a, b}, S = {s₀, s₁},  H = {a, b, <I>, h₀}, F = {s₁} ,

d(s₀, a, h₀) = (s₀, h₀a),                 d(s₀, a, <I>) = (s₀, <I>a),
d(s₀, b, h₀) = (s₀, h₀b),                d(s₀, b, <I>) = (s₀, <I>b),
d(s₀, a, a) = (s₀, aa),                    d*(s₀, a, a<I>a) = (s₀, <I>),
d(s₀, b, a )= (s₀, ba),                   d*(s₀, b, a<I>a) = (s₀, <I>),
d(s₀, a, b) = (s₀, ab),                   d*(s₀, a, b<I>b) = (s₀, <I>),
d(s₀, b, b) = (s₀, bb),                  d*(s₀, b, b<I>b) = (s₀, <I>),
d*(s₀, a, aa) = (s₀, <I>),             d*(s₀, $, a<I>a) = (s₀, <I>),
d*(s₀, b, aa) = (s₀, <I>),             d*(s₀, $, b<I>b) = (s₀, <I>),
d*(s₀, a, bb) = (s₀, <I>),             d*(s₀, $, h₀<I>) = (s₁, $).
d*(s₀, b, bb) = (s₀, <I>),

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

№	Вход	Магазин	Состояние
1.	abba|-	h0	s0
2.	bba|-	h0a	s0
3.	ba|-	h0ab	s0
4.	a|-	h0abb	s0
5.	a|-	h0a<I>	s0
6.	|-	h0a<I>a	s0
7.	|-	h0<I>	s1

---

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