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


Перевод определяемый преобразователем



 

Определение.  
                      Цепочку d

назовем выходом для цепочки c, если существует последовательность  
                      конфигураций, первой из которых является начальная конфигурация с заданной   
                      входной цепочкой c, а последней – заключительная конфигурация с выходной  
                      цепочкой d:                                     (s0, c, h0I, $) |--* (s', $', $, d).

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

D(Mп) = {(x, y) | (s0, c, h0, $) |--* (s', $', $, y) & s' О

F}

   Используя последнее определение, можно определить возможность построения преобразователя, реализующего заданный перевод в виде следующего утверждения.




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