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

Для обозначения множества всех цепочек в алфавите 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

L1, y

L2}.

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

L0 = {e};

Ln = LLn-1, n
1;

L* =

n=0
Ln.

Пример 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, ...}.

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

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

некоторой интерпретацией, связывающей это представление с языком.

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

определение конечного представления ведет только к счетному множеству конечных представлений, поскольку нужно иметь возможность записать такое конечное представление в виде строки символов конечной длины. Поэтому языков значительно больше, чем конечных представлений.

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

Содержание Назад Вперед