Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Примеры. Пусть її = {а, Ь, с}. Рассмотрим язык {а}, состоящий из одного однобуквенного слова 'а'. Обозначим этот язык через а. Тогда произведение
а її*
есть множество всех слов, начинающихся с а.
Вообще, її її* — это множество всех слов, начинающихся с некоторой буквы из її, т. е. множество всех непустых слов:
їїїї* = її* \ {?}.
Операция итерации (операция Клини). Поскольку операция умножения языков ассоциативна, мы можем возводить данный язык L в степень:
L2 = LL; L3 = (LL) L = L (LL) и т. д.
С. К. Клини предложил рассматривать объединение
EULUL2UL3U ... ULnU 26
Часть /. Предварительные сведения из логики и алгебры
всех последовательных степеней языка L1). Это объединение обозначается L* и называется итерацией языка L.
Пример. Мы можем рассматривать алфавит
% = {а, Ь, ...}
как язык, состоящий из однобуквенных слов. Тогда її2 — множество всех диграмм (двухбуквенных слов), її3 — множество всех триграмм и т. д. Поэтому
E U 21U я2 U 2t3 U ...
есть множество всех слов над її, т. е. її*.
Этим и объясняется выбор обозначения її* для свободной полугруппы над її.
Операция обращения. Пусть дан язык Lcr її*; через L обозначается язык, состоящий из обращений всех слов языка L:
L = {X I X є L).
Эта операция является инволютивной (т. е. совпадает со своей обратной операцией):
L = L.
Кроме того, она связана с умножением языков следующим соотношением:
LM= ML.
Пример. Язык її*її* совпадает с її*, поскольку її* = її* и ?є=її*.
§ 1.4. УПРАЖНЕНИЯ
1. Какое соглашение мы неявно принимаем, записывая пустое слово как
E = ''?
Достаньте какое-либо описание Алгола-60 и изучите статус пробела в Алголе.
2. Можно ли сказать о некотором алфавите її, что он содержит «пустую букву»?
3. Пусть имеется алфавит
Я = {а, Ь, с, X, X}.
') По определению La = {?}; вместо {?} пишут обычно Е. — Прим. ред. Гл. I. Слова (цепочки). Полугруппы. Языки
27
Рассмотрим слово
'a Xb Хс = х'.
Имеет ли смысл это выражение, если а, Ь, с и х интерпретируются как числа, X как символ умножения, а = как равенство? Сохраняет ли оно смысл при интерпретации а, Ь, с и х как свободных векторов в евклидовом пространстве, а X—как векторного произведения? Какой вывод, относящийся к конкатенации, можно сделать из сравнения этих двух случаев?
4. Рассмотрим множество 5 = {А, В, С, ...}, снабженное операцией композиции (которую мы обозначим точкой); на множестве5 определена эквивалентность, совместимая слева и справа с этой операцией, т. е. конгруэнция. _
1°) Обозначим через Л класс элемента А, через В — класс элемента В и т. д. Доказать, что класс композиции A-B зависит только от Л и Б\ показать, что можно определить композицию классов следующим образом:
А ¦ B = A B.
2°) Проверить ассоциативность композиции классов: (A-B)-C = = A-(B-C), исходя из ассоциативности компоцизии в S, т. е. выбирая в каждом классе элемент-представитель.
3°) Пусть Е — единичный элемент в 5 относительно композиции и Ё — класс элемента Е. Доказать, что
A -E = E -A = А.
(Аналогично п. 2° взять в Л элемент-представитель.)
5. Пусть имеется алфавит {а, Ь, с} и следующая система соотношений:
аа~Е; bb~E-, ab~ba.
Разрешима ли в этом случае проблема эквивалентности?
6. Пусть имеется алфавит {а, Ь, с} и следующая система соотношений:
(1) ааа~Е\ (2) Ьа~аЬ\ (3) са~ас.
Что можно сказать о словах 'aabaca' и 'abc'?
Вообще, разрешима ли для этого конкретного исчисления проблема эквивалентности слов?
7. Пусть слова А, В, С, D таковы, что
AB = CD и |Л|<|С|. 28
Часть /. Предварительные сведения из логики и алгебры
Доказать, что существует слово X, такое, что
C = AX и B = XD.
8. Слово M называется периодическим, если оно может быть получено конкатенацией одинаковых слов. Самое короткое слово, повторением которого можно получить М, называется основанием слова М.
Рассмотрим непустые слова U и V, такие, что UV = VU. Доказать, что U и V являются периодическими и имеют одно и то же основание.
Для решения этой задачи можно воспользоваться следующими указаниями.
Докажите, что для любого целого числа k
U ... U -V ...V = V ...V -U ... U.
k раз k раз k раз k раз
Рассмотрите наименьшее общее кратное длины слова U и длины слова V, выберите k и докажите, что U и V являются периодическими. Выяснить, что можно сказать об их основании.
9. 1°) Пусть непустые слова А и В таковы, что для некоторых m и п слова Am и Bn начинаются одним и тем же сегментом длины |А| + |?|. Доказать, что либо A=B, либо А и В являются периодическими и имеют одно и то же основание (воспользоваться предыдущим упражнением).
2°) Доказать, что если Am = Bn, m, п > 1, то А и В являются периодическими и имеют одно и то же основание.
3°) Доказать, что если А не пусто, то существует натуральное число k и непериодическое («простое») слово В, такие, что А = Bk.
10. Исследовать равенство
AX = XB.
11. Пусть дан алфавит її; рассмотрим функцию ф, определенную на множестве слов в алфавите її и принимающую значения из этого множества.
