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

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


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


 

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


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

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

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

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



      Содержание раздела