С помощью понятия выводимая пара можно определить перевод, задаваемый
СУ - схемой.
Определение. Переводом С(T), определяемым СУ-схемой Т назовем множество пар, состоящих из входной и выходной цепочек, выводимых из пары, включающей два начальных символа. С(T) = {(a
,b ) | (<I>,<I>) ==>* (a
,b ) и a О
Vтвх*,
b О
Vтвых*}
|
T4.1: Va = {<I>,<A>}, Vтвх = {0,1},Vтвых = {a,b}
Q = { <I> ╝ 0<A><I>,
<I><A>a;
<A> ╝ 0<I><A>, <A><I>a;
<I> ╝ 1, b;
<A> ╝ 1, b
}.
Эта схема определяет перевод, входные слова которого состоят из нулей
и единиц, а выходные из букв а,b. Нулям входной цепочки должны соответствовать
буквы a, а единицам - буквы b выходной цепочки, причем расположение символов
в выходной цепочке должно быть
зеркальным по отношению к соответствующим символам входной цепочки.
Вывод в рассматриваемой СУ - схеме может, например, иметь вид:
==>(0<A>00<I><A><I>,<I><A><I>aa<A>a)==>*==>*(0100111,bbbaaba)