Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
CT = CT+- ст~.
Системе (F') мы можем поставить в соответствие две грамматики: G+ с аксиомой S+ и G- с аксиомой На этом примере мы разъясним понятие вычитания языков.
Рассмотрим две КС-грамматики G+ и G-, порождающие цепочки с определенными степенями неоднозначности. Будем считать, что «грамматика» G+—G~ порождает цепочки как с положительными, так и с отрицательными степенями неоднозначности, причем с положительными степенями неоднозначности в «язык», порождаемый грамматикой G+—G- (иначе — в разность языков), войдут цепочки из L(G+), с отрицательными — из L(G~)\ если цепочка / порождается обеими грамматиками, то ее степень неоднозначности относительно G+—G- равна а—?, где а и ? — степени неоднозначности / относительно G+ и G- соответственно.
Разложение, аналогичное построенному в этом примере, можно произвести и в общем случае: всякой системе уравнений с целыми — положительными и отрицательными — коэффициентами можно поставить в соответствие две системы уравнений с положительными коэффициентами так, что данная система будет соответствовать их разности.
Пример. Пусть язык
/m = {flW I п^0} порождается уравнением
5 = aSa + с. Гл. XVI. Алгебраические языки
261
Обозначим через Lm язык, порождаемый уравнением (G): S = aSa + S — akcak, где k — постоянная.
Язык Lrm можно получить как разность языков, задаваемых уравнениями
(G+): S+=aS+a + c, (G~): S~ = aS~a + akcak, L(G+): {ancan | n> 0}, L{G~): {ancan I Lfm = L(G+) - L (G") = {ancan \ 0 <n<&}.
Язык Lfm конечен; применяя к (G) метод последовательных приближений, можно видеть, что все цепочки, содержащие BXO-• ждение подцепочки ohcoh, в конце концов исчезают.
16.3.2. Рациональные языки
В п. 16.1.8 мы видели, что кольцо Z [[X*]] содержит всевозможные частные вида ^ • • хт) ^ где р^ q — многочлены, а в Q
Q [X], . . ., Xm)
коэффициент при пустой цепочке равен 1 (или —1).
Опорные множества таких рядов являются рациональными языками-, они соответствуют случаю, когда систему уравнений можно решить с помощью техники «первой степени».
Правые части соответствующих уравнений представляют собой линейные функции неизвестных; коэффициенты расположены с одной стороны от последних.
Пример. Вычисление некоммутативных рациональных функций. Рассмотрим систему уравнений
Будем обозначать единицу через 1. Уравнение (2) дает
А = ЬВ-сС + с, В = abB + с А, С = ЬА —сС.
(О (2) (3)
г Л
(1 -ab)B = cA, откуда В = j~- = (l + (ab)*) с А.
Аналогично, уравнение (3) дает
(1 +с)С = ЬА, C = -f^ = (l+(-cY)bA.
ЬА 262
Часть III. Алгебраический подход
Подставляя полученные значения В и С в (1), имеем A = b (\ + (ab)') сА-с( 1+(- с)')ЬА + с, [1 -Ь( 1 + (ab)*) с + с (1 + ( — c)*)b] A = C.
Поэтому
А =_і_
1 - Ь (1 + (аЬУ) с + с (1 + (- с)') Ь '
откуда получаются выражения для В и С.
Данное вычисление оказалось возможным лишь благодаря тому, что входящие в уравнения одночлены имеют специальный вид; все они линейны относительно неизвестных и все их коэффициенты стоят с одной и той же стороны от неизвестных. Зго последнее свойство исключает неоднородность размещения множителей и делителей: если в уравнениях системы встречаются двусторонние одночлены или одночлены и типа аЛ, и типа Aa, то выражения вида
допускают две различные интерпретации: либо 6(1 + а*), либо (1 + а*)Ь.
16.3.3. Алгебраические языки
Опорное множество алгебраического ряда является алгебраическим языком.
Два признака: «произвольный/алгебраический» и «коэффициенты являются положительными/произвольными целыми», позволяют различать четыре класса языков:
шиеся КС-языками. Гл. XVI. Алгебраические языки
263
16.3.4. Адамаровское произведение рядов
Среди основных операций над языками есть одна, которую мы до сих пор не интерпретировали в терминах рядов, — это операция пересечения. Для такой интерпретации можно использовать понятие адамаровского произведения. Напомним определение адама-ровского произведения двух рядов (с коммутативными переменными).
Пусть имеются функции fug, заданные разложением в целочисленные ряды:
/ = а0 + O1* + а2х2 + ... + апх" + ...,
g = ba + blx + b2x2+ ... +Ьпхп+ ....
Адамаровским произведением fQg рядов fug называется выражение
fQg = a0b0 + alblx + a2b2x2 + ... +anbnxn+ ....
Для функций одной переменной имеет место следующая
Теорема (Юнген). а) Если f — рациональная функция и g — рациональная функция, то fQg— тоже рациональная функция.
б) Если f — рациональная функция и g — алгебраическая функция, то fQg — алгебраическая функция.
в) Если f — алгебраическая функция и g — алгебраическая функция, то fQg может не быть алгебраической функцией.
Теперь мы обобщим понятие адамаровского произведения следующим образом. Пусть сті и о2— формальные ряды с некоммутативными переменными, и / обозначает произвольную цепочку, принадлежащую опорным множествам обоих рядов сті и ст2; пусть, кроме того, а и ? — степени неоднозначности цепочки f в о\ и O2 соответственно. Тогда
CiOtf2 = 2 a?/. f
