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


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


    Для описания работы магазинного преобразователя необходимо дать его определение.


 

Определение:


Преобразователем с магазинной памятью (Мп) называется совокупность восьми 
                             объектов: 

Мп={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

      О Hp О

      Pb

      О H*, e

      О W*

      и s,s' О S.

 


Определим конфигурацию Мп как четверку

              (s, ac, rh, d),

где ac

О P*, rh

О H*

и d

О W*.


Если такту работы преобразователя соответствует конфигурация (s, ac, rh , d) и определена функция переходов j(s, a, h) = (s', b, e), то происходит смена конфигурации, которую условимся записывать так:

       

          (s, ac,

          rh, d) |-- (s', c, rb,

          de).

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

на ленте, цепочка h0I в магазине, начальное состояние s0

и пустая цепочка на выходной ленте:


(s0, c, h0I, $).
    Конечной или заключительной конфигурацией назовем четверку (sk, $, $, d), где sk

- одно из заключительных состояний из множества F, а d

- выходная цепочка.

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




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