Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Ясно, что единичный класс будет получен тогда и только тогда, когда канонические представители являются обращениями друг друга.
Любой класс допускает единственное обращение, одно и то же влево и вправо, откуда — пары взаимно обратных слов:
Е, Е; а, а; b, b\ ab, ba-, aba, aba-, bab, bab-, abab, baba\ .... Гл. I. Слова (цепочки). Полугруппы. Языки
23
Класс, имеющий своим представителем симметричное сокращенное слово, является своим собственным обращением.
Читатель уже заметил, по-видимому, что в данном случае полугруппа классов является группой.
Что касается ядра (множества слов класса Е), то оно включает симметричные слова четной длины, а также слова, полученные конкатенацией этих последних, например:
baab, abba, bb. § 1.3. языки
1.3.1. Определение
Формальным языком, определенным на базовом множестве її, называется любое подмножество свободной полугруппы її*, иначе— любое множество цепочек из элементов її. Для краткости мы будем говорить просто «язык», опуская прилагательное «формальный».
Примеры. Для любого її множество слов четной длины является языком; множество слов нечетной длины также является языком, но другим: первый язык замкнут относительно операции конкатенации, а второй нет.
Для любого її множество симметричных слов является языком, не замкнутым относительно конкатенации (кроме случая, когда її состоит из одной буквы).
1.3.2. Один важный пример: языки Дика
Представим себе набор формул некоторого математического исчисления или программу, записанную на языке типа Алгола. Это будет текст, в котором, видимо, будут встречаться знаки, всегда употребляемые только попарно: левые и правые скобки всех видов (круглые, квадратные, фигурные, ломаные) или такие выражения, как begin — end и т. п. Выкинем из текста все, кроме знаков указанного типа. Получится новый текст, построенный по некоторым строгим правилам.
Пример. Возьмем следующую правильную алгебраическую формулу:
{[(а + Ь) {с + d) - {а' + b') (c' + d')f - (abed - a'b'c'd'ff -
- {[(аа' + bb' + с с' + dd'f + {abcda'b'c'd')'h\ + A\\
Указанным способом из нее можно получить выражение {[()()()()]()}{[()()]}.
Подобные тексты дают представление об ограниченных языках Дика, 24
Часть /. Предварительные сведения из логики и алгебры
Интерес к языкам Дика объясняется (по крайней мере отчасти) тем, что они очевидным образом связаны со скобочными структурами, обычными для естественных и искусственных языков (логика, математика, языки программирования и т. д.).
Перейдем к точным определениям.
Определения. Пусть її = [a, a', b, b', ...} — алфавит, состоящий из 2п букв, объединяемых в пары: а, а'\ b, b'\ ...; пусть E — пустое слово, и пусть даны соотношения Туэ:
аа' ~Е\ bb' ~Е; ....
Слово X принадлежит ограниченному языку Дика над її тогда и только тогда, когда оно эквивалентно в смысле этих соотношений пустому слову.
Аналогичным образом определяется неограниченный язык Дика\ при этом берутся соотношения
аа'~а'а~Е, bb'~b'b~E, ... .
Примеры. Слово abb'a'cc' принадлежит ограниченному языку Дика.
Слово a'ab'cc'b принадлежит языку Дика.
1.3.3. Операции над языками
Пусть її — некоторый алфавит и її* — свободная полугруппа над її. Поскольку (формальные) языки над її являются подмножествами множества її*, можно определить в множестве подмножеств из її* [это множество мы будем обозначать через $(її*)] некоторые теоретико-множественные операции. Рассмотрим основные операции этого типа.
Объединение языков. Пусть даны два языка Li и L2. Объединением этих языков (обозначение: L\ U L2) называется множество всех слов, принадлежащих хотя бы одному из языков.
Эта операция представляет собой обычное теоретико-множественное объединение; она коммутативна и ассоциативна:
L1UL2 = L2UL1, (L1UL2)UL3 = L1U(L2UL3).
Пересечение языков. При тех же условиях пересечением двух языков (обозначение: L1 П L2) называется множество всех слов, принадлежащих одновременно обоим языкам.
Эта операция представляет собой обычное теоретико-множест-венное пересечение; она тоже коммутативна и ассоциативна.
Дополнение. Дополнением языка L до її* (обозначение: її* \ L) называется множество всех слов, принадлежащих її*, но не принадлежащих L1 Гл. I. Слова (цепочки). Полугруппы. Языки
25
Само множество її* есть язык, дополнением которого до її* является пустой язык.
Подчеркнем, что язык, содержащий пустое слово Е, не является пустым.
Пример.
я = R ьу,
L = {ambn\m^\, Пі
%*\L = (L\ UL2UL3), где Li — множество всех слов, начинающихся с b, L2 — множество всех слов, начинающихся с атЬпа, и I3 = {а}*, т. е. L3 есть множество всех слов, состоящих только из а.
Умножение языков. При тех же условиях, что и выше, произведением двух языков (обозначение: LtL2) называется множество всех слов, которые можно получить следующим способом: берется некоторое слово из Li и к нему присоединяется конкатенацией справа некоторое слово из L2, т. е.
L\L2 = I^i є > X2^ L^}.
Эта операция (называемая умножением языков) не совпадает с декартовым умножением; она ассоциативна, но не коммутативна.
