Алфавиты, цепочки и языки

Алфавит, или словарь - это конечное множество символов. Для обозначения символов мы будем пользоваться цифрами, латинскими буквами и специальными литерами типа

Пусть V - алфавит. Цепочка в алфавите V - это любая строка конечной длины, составленная из символов алфавита V . Синонимом цепочки являются предложение, строка и слово. Пустая цепочка (обозначается e) - это цепочка, в которую не входит ни один символ.

Конкатенацией цепочек x и y называется цепочка xy. Заметим, что xe = ex = x для любой цепочки x.

Пусть x, y, z - произвольные цепочки в некотором алфавите. Цепочка y называется подцепочкой цепочки xyz. Цепочки xи y называются, соответственно, префиксом и суффиксом цепочки xy. Заметим, что любой префикс или суффикс цепочки является подцепочкой этой цепочки. Кроме того, пустая цепочка является префиксом, суффиксом и подцепочкой для любой цепочки.

Пример 2.1. Для цепочки abbba префиксом является любая цепочка из множества суффиксом является любая цепочка из множества подцепочкой является любая цепочка из множества

Длиной цепочки w (обозначается |w| ) называется число символов в ней. Например, |abababa| = 7, а |e| = 0. Язык в алфавите V - это некоторое множество цепочек в алфавите V.

Пример 2.2. Пусть дан алфавит V = {a, b}. Вот некоторые языки в алфавите V:

1. — пустой язык;

2. - язык, содержащий только пустую цепочку (заметим, что и - различные языки)

3. - язык, содержащий цепочки из a и b, длина которых не превосходит 2

4. - язык, включающий всевозможные цепочки из a и b, содержащие четное число a и четное число b

5. - язык цепочек из a, длины которых представляют собой квадраты натуральных чисел.

Два последних языка содержат бесконечное число цепочек.

Введем обозначение для множества всех цепочек в алфавите , включая пустую цепочку. Каждый язык в алфавите V является подмножеством . Для обозначения множества всех цепочек в алфавите V , кроме пустой цепочки, будем использовать .

Пример 2.3. Пусть . Тогда

Введем некоторые операции над языками.

Пусть и - языки в алфавите V. Конкатенацией языков и называется язык .

Пусть L - язык в алфавите V. Итерацией языка L называется язык , определяемый следующим образом:

( 1)

( 2)

( 3)

Пример 2.4. Пусть и . Тогда

, и

Большинство языков, представляющих интерес, содержат бесконечное число цепочек. При этом возникают три важных вопроса.

Во-первых, как представить язык (то есть специфицировать входящие в него цепочки)? Если язык содержит только конечное множество цепочек, ответ прост. Можно просто перечислить его цепочки. Если язык бесконечен, необходимо найти для него конечное представление. Это конечное представление, в свою очередь, будет строкой символов над некоторым алфавитом вместе с некоторой интерпретацией, связывающей это представление с языком.

Во-вторых, для любого ли языка существует конечное представление? Можно предположить, что ответ отрицателен. Мы увидим, что множество всех цепочек над алфавитом счетно. Язык - это любое подмножество цепочек. Из теории множеств известно, что множество всех подмножеств счетного множества несчетно. Хотя мы и не дали строгого определения того, что является конечным представлением, интуитивно ясно, что любое разумное определение конечного представления ведет только к счетному множеству конечных представлений, поскольку нужно иметь возможность записать такое конечное представление в виде строки символов конечной длины. Поэтому языков значительно больше, чем конечных представлений.

В-третьих, можно спросить, какова структура тех классов языков, для которых существует конечное представление?