306 Глава 7. Приложения
де, где форматированием выделены операторы и идентифи-
каторы, логические операторы представлены математически-
ми символами («¬»,«∧»,«∨»), оператор присваивания показан
в виде «←» и т. п.
Также мы приводим в тексте только ключевую часть ал-
горитма, различные вспомогательные функции (инициализа-
ция данных, печать и вывод иллюстраций и т. п.) остаются за
скобками. Все это сделано, чтобы максимально избавить текст
алгоритма от технических подробностей, но все же это насто-
ящие, работающие алгоритмы, и трассировка их вывода полу-
чена при выполнении программы.
7.2. Глоссарий
По результатам чтения лекций, были выявлены основные обо-
значения, вызывающие у студентов затруднения. Они приведе-
ны в виде справочного материала.
Определение 7.2.1. Алфавит — конечный набор символов.
Определение 7.2.2. Слово — конечная последовательность
символов из некоторого алфавита Σ.
Пустое слово обозначается ∅. Набор слов длины n над ал-
фавитом Σ обозначается Σ
n
, набор всех слов (включая пу-
стое) — Σ
∗
.
Определение 7.2.3. Язык L — произвольное подмножество
L ⊆ Σ
∗
, т. е. произвольное множество слов над алфавитом Σ.
Надо отличать пустой язык (язык не содержащий ни одного
слова), который также обозначается ∅, от языка {∅}, содержа-
щего единственное пустое слово.
Определение 7.2.4. Дополнение языка L — язык L, состо-
ящий из всех возможных слов над алфавитом Σ, не входящих
в язык L —
L ≡ Σ
∗
\ L.