Математическая теория формальных языков

       

Формальные языки


Определение 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. Пусть даны такие алфавиты и , что . В каком случае ?



Содержание раздела