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

4.3.2. Описание работы магазинного преобразователя.

    Для описания работы магазинного преобразователя необходимо дать его определение.
 
Определение:
Преобразователем с магазинной памятью (Мп) называется совокупность восьми 
                             объектов: 
Мп={P, S, s0, H, h0, F, W, q},
       где P - входной алфавит, состоящий из символов, записываемых на входную ленту; 
    W - выходной алфавит, содержащий символы, записываемые на выходную ленту; 
        H - магазинный алфавит, содержащий символы, записываемые и считываемые из     магазина; 
h0 - маркер дна магазина, он принадлежит H; 
S - множество состояний преобразователя; 
s0- начальное состояние из множества S; 
F - множество конечных состояний, представляющих собой подмножество S; 
j - функция переходов преобразователя, которая задает отображение, 
            j: Sx{P И {$} x H Ю S x H* x W* .
      Она может быть записана в функциональном виде:  
              j(s, p, h) = (s', b, e), 
        
      где h О H,  p О P,  b О H*, e О W* и s,s' О S.
 
Определим конфигурацию Мп как четверку

где ac О P*, rh О H* и d О W*.
Если такту работы преобразователя соответствует конфигурация (s, ac, rh , d) и определена функция переходов j(s, a, h) = (s', b, e), то происходит смена конфигурации, которую условимся записывать так: Последовательность сменяющих друг друга конфигураций, как обычно, обозначим символом |--*. В качестве начальной примем конфигурацию, которой соответствует заданная входная цепочка c на ленте, цепочка h0I в магазине, начальное состояние s0 и пустая цепочка на выходной ленте:
(s0, c, h0I, $).
    Конечной или заключительной конфигурацией назовем четверку (sk, $, $, d), где sk - одно из заключительных состояний из множества F, а d - выходная цепочка.

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

 

Hosted by uCoz