Алфавиты, цепочки и языки
Алфавит, или словарь - это конечное множество символов. Для обозначения символов мы будем пользоваться цифрами, латинскими буквами и специальными литерами типа #, $.
Пусть V - алфавит. Цепочка в алфавите V - это любая строка конечной длины, составленная из символов алфавита V . Синонимом цепочки являются предложение, строка и слово. Пустая цепочка (обозначается e) - это цепочка, в которую не входит ни один
символ.
Конкатенацией цепочек x и y называется цепочка xy. Заметим, что xe = ex = x для любой цепочки x.
Пусть x, y, z - произвольные цепочки в некотором алфавите. Цепочка y называется подцепочкой цепочки xyz. Цепочки x и y называются, соответственно, префиксом и суффиксом цепочки xy. Заметим, что любой префикс или суффикс цепочки является подцепочкой этой цепочки. Кроме того, пустая цепочка является префиксом, суффиксом и подцепочкой для любой цепочки.
Пример2.1. Для цепочки abbba префиксом является любая цепочка
из множества L1 = {e, a, ab, abb, abbb, abbba}, суффиксом является любая цепочка из множества L2 = {e, a, ba, bba, bbba, abbba}, подцепочкой является любая цепочка из множества L1
Длиной цепочки w (обозначается |w|) называется число символов в ней. Например, |abababa| = 7, а |e| = 0.
Язык в алфавите V - это некоторое множество цепочек в алфавите V .
Пример 2.2. Пусть дан алфавит V = {a, b}. Вот некоторые языки в алфавите V :
- L1 = - пустой язык;
- L2 = {e} - язык, содержащий только пустую цепочку
(заметим, что L1 и L2 - различные языки);
- L3 = {e, a, b, aa, ab, ba, bb} - язык,
содержащий цепочки из a и b, длина которых не превосходит 2;
- L4 - язык, включающий всевозможные цепочки из a и b, содержащие четное число a и четное число b;
- L5 = {an2
|n > 0} - язык цепочек из a, длины которых представляют собой квадраты натуральных чисел.
Два последних языка содержат бесконечное число цепочек.
Введем обозначение V *
для множества всех цепочек в алфавите V , включая пустую цепочку. Каждый язык в алфавите V является подмножеством V *.
Для обозначения множества всех цепочек в алфавите V , кроме пустой цепочки, будем
использовать V +.
Пример 2.3. Пусть V = {0, 1}. Тогда V * = {e, 0, 1, 00, 01, 10, 11, 000, ...}, V + = {0, 1, 00, 01, 10, 11, 000, ...}.
Введем некоторые операции над языками.
Пусть L1 и L2
- языки в алфавите V . Конкатенацией языков L1 и L2
называется язык L1L2 = {xy|x
Пусть L - язык в алфавите V . Итерацией языка L называется язык L*, определяемый следующим образом:
- L0 = {e};
- Ln = LLn-1, n 1;
- L* =
n=0Ln.
Пример 2.4. Пусть L1 = {aa, bb} и L2 = {e, a, bb}. Тогда
L1L2 = {aa, bb, aaa, bba, aabb, bbbb}, и
L1* = {e, aa, bb, aaaa, aabb, bbaa, bbbb, aaaaaa, ...}.
Большинство языков, представляющих интерес, содержат бесконечное число цепочек. При этом возникают три важных вопроса.
Во-первых, как представить язык (т.е. специфицировать входящие в него цепочки)? Если язык содержит только конечное множество цепочек, ответ прост. Можно просто перечислить его цепочки. Если язык бесконечен, необходимо найти для него конечное представление. Это конечное представление, в свою очередь, будет строкой символов над некоторым алфавитом вместе с
некоторой интерпретацией, связывающей это представление с языком.
Во-вторых, для любого ли языка существует конечное представление? Можно предположить, что ответ отрицателен. Мы увидим, что множество всех цепочек над алфавитом счетно. Язык - это любое подмножество цепочек. Из теории множеств известно, что множество всех подмножеств счетного множества несчетно. Хотя мы и не дали строгого определения того, что является конечным представлением, интуитивно ясно, что любое разумное
определение конечного представления ведет только к счетному множеству конечных представлений, поскольку нужно иметь возможность записать такое конечное представление в виде строки символов конечной длины. Поэтому языков значительно больше, чем конечных представлений.
В-третьих, можно спросить, какова структура тех классов языков, для которых существует конечное представление?