Стр. 72 - Информационные структуры и их преобразование

70 Содержание
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
5. ТЕОРИЯ ПЕРЕВОДА
5.1. Формализмы определения перевода
Перевод (трансляция) – это некоторое отношение между цепочками,
т.е. некоторое множество пар цепочек. Существует два метода определения
перевода:
1. Схема перевода – грамматика, снабженная механизмом,
обеспечивающим выходную цепочку для каждой порождаемой.
2. Распознаватель с выходом , который на каждом такте
анализируемой цепочки в алфавите Σ может выдать цепочку ограниченной
длины в алфавите ∆.
Пусть:
Σ - входной алфавит;
∆ - выходной;
∗ ∗ ∆∈ Σ∈
2 1 L, L .
Тогда переводом языка L1 в L2 назовем отношение Т, такое, что
∗ ∗ ∆→Σ, где
L1 – область определения,
L2 – множество значений.
Если ( ) T y,x ∈ , то цепочка х – входная, а у – выходная.
В общем случае в переводе Т для каждой входной цепочки может быть
более одной выходной, однако в языках программирования перевод должен
быть с однозначной функцией.
Рассмотрим следующий пример: пусть требуется греческий алфавит
перевести в русский:
Греческий алфавит Русский алфавит
Α, α Альфа
Β, β Вета
Такой тип перевода называется гомоморфизмом, он для
программирования не приемлем.