Теория и реализация языков программирования



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


Конкатенацией языков
L_1
и
L_2
называется язык
L_1L_2 = \{xy|x \in L_1, y \in L_2\}
.

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

L^*
, определяемый следующим образом:

L^0=\{|e\}

(1)

L^n = LL^{n-1}, n \geq1

(2)

L^*=\bigcup\limits^\infty_{n=0} L^n

(3)

Пример 2.4. Пусть

L_1 = \{aa, bbg\}
и
L_2 = |{e, a, bb\}
. Тогда

L_1L_2=|{aa, bb, aaa, bba, aabb, bbbb\}
, и

L^*_1=\{e, aa, bb, aaaa, aabb, bbaa, bbbb, aaaaaa, \ldots\}

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

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

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

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




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