В общем случае перевод или трансляцию можно представить как соответствие между словами алфавита Р и алфавита W. Если цепочка a О P* , цепочка b О W* , они называются соответственно входной и выходной цепочками.

С = {(a,00),(b,01),(c,10),(d,11),(ab,0001),(ac,0010),

         (cd,0011),(bc,0110),(bd,0111),(cd,1011) }.

Конечные переводы с небольшим числом элементов можно задавать в виде перечислений. Однако, для задания больших конечных переводов и бесконечных переводов нужны такие
же средства задания как и для формальных языков. Рассмотрим случай , когда множество входных цепочек  (входной язык перевода С) можно задать с помощью грамматики Г и множества выходных цепочек (выходной язык перевода С) - с помощью грамматики Г'.
Примером такого задания может служить перевод, определяющий для каждой входной цепочки a ее зеркальное отображение a ". Если входной и выходной алфавиты состоят из двух символов - {0,1}, то правила построения такого перевода имеют вид:

        входные цепочки                      выходные цепочеки

1)          <I> ╝ 0<I>,                                 <I> ╝ <I>0
2)          <I> ╝ 1<I>,                                 <I> ╝ <I>1
3)          <I> ╝ $,                                       <I> ╝ $

 
Применяя одновременно соответствующие правила  построения к входной и выходной цепочкам, получаем:

(<I>,<I>) ==> (0<I>,<I>0) ==> (00<I>,<I>00) ==>  (001<I>,<I>100) ==> (001,100)

При таком построении существенное значение имеет заданное соответствие между правилами построения входных и выходных цепочек.

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