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

Определение 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}.

Дата добавления: 2015-07-26; просмотров: 148; Нарушение авторских прав

Мы поможем в написании ваших работ!