Математическая теория формальных языков
Формальные языки
Определение 1.1.1. Будем называть натуральными числами
неотрицательные целые числа. Множество всех натуральных чисел {0, 1, 2, ...} обозначается N.
Определение 1.1.2. Алфавитом называется конечное непустое множество. Его элементы называются символами (буквами).
Определение 1.1.3.Словом (цепочкой, строкой, string) в алфавите
называется конечная последовательность элементов .
Пример 1.1.4. Рассмотрим алфавит = {a, b, c}. Тогда baaa является словом в алфавите .
Определение 1.1.5. Слово, не содержащее ни одного символа (то есть последовательность длины 0), называется пустым словом
и обозначается .
Определение 1.1.6. Множество всех слов в алфавите
обозначается .
Замечание 1.1.7. Множество счетно. В самом деле, в алфавите
множество всех слов данной длины конечно, следовательно,
является объединением счетного числа конечных множеств.
Определение 1.1.8. Множество всех непустых слов в алфавите
обозначается .
Пример 1.1.9. Если = {a}, то = {a,aa,aaa,aaaa,...}.
Определение 1.1.10.
Если , то L называется языком
(или формальным языком) над алфавитом .
Поскольку каждый язык является множеством, можно рассматривать операции объединения, пересечения и разности языков, заданных над одним и тем же алфавитом (обозначения ).
Пример 1.1.11. Множество {a, abb} является языком над алфавитом {a, b}.
Определение 1.1.12. Пусть . Тогда язык
называется дополнением языка L относительно алфавита . Когда из контекста ясно, о каком алфавите идет речь, говорят просто, что язык
является дополнением языка L.
Определение 1.1.13.
Если x и y - слова в алфавите , то слово xy (результат приписывания слова y в конец слова x) называется конкатенацией, (катенацией, сцеплением) слов x и y. Иногда конкатенацию слов x и y обозначают .
Определение 1.1.14.
Если x - слово и , то через xn
обозначается слово . Положим (знак читается "равно по определению"). Всюду далее показатели над словами и символами, как правило, являются натуральными числами.
Пример 1.1.15. По принятым соглашениям ba3 = baaa и (ba)3 = bababa.
Пример 1.1.16.
Множество
является языком над алфавитом {a,b}. Этот язык содержит слова b, ba, aba, baa, abaa, baaa, aabaa, abaaa, baaaa и т. д.
Определение 1.1.17. Длина слова w, обозначаемая |w|, есть число символов в w, причем каждый символ считается столько раз, сколько раз он встречается в w.
Пример 1.1.18. Очевидно, что |baaa| = 4 и .
Определение 1.1.19. Через |w|a обозначается количество вхождений символа a в слово w.
Пример 1.1.20.
Если , то |baaa|a = 3, |baaa|b = 1 и |baaa|c = 0.
Упражнение 1.1.21. Перечислить слова языка , где
и .
Упражнение 1.1.22. Пусть . Равны ли языки
и ?
Упражнение 1.1.23. Пусть ,
и . Сколько слов содержит язык L1 - L2?
Упражнение 1.1.24. Пусть даны такие алфавиты и , что . В каком случае ?
