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

UptoLike

ВУЗ: 

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

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

Рубрика: 

8
Часть I: ЯЗЫКИ, ГРАММАТИКИ, АВТОМАТЫ
Глава 1
ЯЗЫКИ ИХ ПРЕДСТАВЛЕНИЕ
§ 1.1. Алфавиты и языки
Приступая к изучению теории языков, прежде всего, следует определить,
что мы подразумеваем под термином язык. Энциклопедическое определение
языка как ”важнейшего средства общения, обмена мыслями и взаимного
понимания в человеческом обществе”
1
недостаточно для построения математи-
ческой теории языков. Поэтому мы определим язык абстрактно — как
математическую систему. Это даст нам возможность делать строгие
утверждения о формальных языках, которые надлежащим образом будут
моделироваться. С этой мыслью мы дадим следующие определения.
Определение 1.1. Алфавит или словарь есть конечное не пустое множество
символов.
Что такое символ — не определяется, как не определяется, например, точка
в геометрии.
Некоторые примеры алфавитов:
латинский {a, b, …, z, A, B, ..., Z}
греческий {α, β, ..., ω, Α, Β, …, Ω}
бинарный {0, 1}.
Определение 1.2. Предложение (строка, слово) есть любая цепочка
конечной длины, составленная из символов алфавита. Цепочка, не содержащая
ни одного символа, называется
пустым предложением. Оно обозначается
греческой буквой
ε.
Если
V — некоторый алфавит, то V
*
обозначает множество всех
предложений, составленных из символов алфавита
V, включая и пустое
предложение.
Будем обозначать посредством
V
+
множество V
*
\ {ε}. Так, например, если
V = {0, 1}, то V
*
= {ε, 0, 1, 00, 01, 10, 11, 000, ...}, а V
+
= {0, 1, 00, 01, 10, 11, ...}.
Если
x∈ V
*
, то |x | обозначает длину цепочки x, т. е. число символов, её
составляющих. Естественно считать, что длина пустой цепочки
ε равна 0.
Определение 1.3. Язык есть любое множество предложений над некоторым
алфавитом. Формально, если
V — алфавит, L — язык, то L ⊆ V
*
.
Естественно возникают три вопроса:
1. Как представить язык, т.е. как определить предложения, составляющие
язык?
2. Для каждого ли языка существует конечное представление?
3. Какова структура тех классов языков, для которых существуют конечные
представления?
1
Энциклопедический словарь. — М.: Большая советская энциклопедия, 1955. С. 716.

Страницы