Языки и трансляции. Мартыненко Б.К. - 139 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

137
Часть II: ТРАНСЛЯЦИИ И СИНТАКСИЧЕСКИЕ
МЕТОДЫ ИХ РЕАЛИЗАЦИИ
Глава 1
ТРАНСЛЯЦИИ,
ИХ ПРЕДСТАВЛЕНИЕ И РЕАЛИЗАЦИЯ
§ 1.1. Трансляции и трансляторы
Определение 1.1. Трансляцией из языка L
1
⊆Σ
*
в язык L
2
⊆∆
*
называется
отношение τ⊆L
1
× L
2
. Здесь Σ — входной алфавит, L
1
— входной язык, ∆ —
выходной алфавит, L
2
— выходной язык.
Другими словами, трансляция есть некоторое множество пар предложений
(x, y), где x∈L
1
— входное, а y ∈L
2
— выходное предложение. Хотя в общем
случае в трансляции τ одному входному предложению x может соответствовать
несколько выходных предложений y, по отношению к языкам программиро-
вания трансляция всегда является функцией, т.е. для каждого входа существует
не более одного выхода.
Существует бесконечно много примеров трансляций, но самым элементар-
ным, вероятно, является тот, который демонстрирует задание трансляции
гомоморфизмом, т.е. отображением h из Σ в ∆
*
.
Пример 1.1. Предположим, что мы хотим закодировать некоторый текст с
помощью азбуки Морзе. Как известно, в коде Морзе каждая буква представ-
ляется как некоторая последовательность из точек и тире. Эти последователь-
ности, называемые посылками, имеют разную длину. Для отделения одной
посылки от другой используется пауза. Очевидно, что трансляцию предло-
жений, например, на русском языке, в код Морзе можно реализовать с
помощью гомоморфизма, задаваемого следующим образом:
Буква а б в … я
Посылка
⋅
⋅ ⋅ ⋅
⋅
…
⋅ ⋅
Для простоты предполагаем, что паузы представлены пробелами, завершаю-
щими
каждую посылку. Тогда, скажем, слово “абба” с помощью замены букв на
посылки даёт следующий результат:
⋅
⋅ ⋅ ⋅
⋅ ⋅ ⋅
⋅
Для любой входной цепочки x = a
1
a
2
…a
n
, a
i
∈Σ, i = 1, 2,…, n, гомомор-
физм h позволяет найти соответствующую выходную цепочку y с помощью
посимвольной подстановки: y = h(a
1
)h(a
2
)…h(a
n
).
Область определения гомоморфизма можно расширить до Σ
*
следующим
образом: h(ax)=h(a)h(x), h(ε)=ε. Здесь a ∈Σ, x ∈Σ
*
.

Страницы