Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
тах(л, 1, cF(n)). Если при этом Г — НС-, сответственяо Б-грам-матика, то и Г' можно сделать НС (Б)-грамматикой.
2.9. Пусть F(T,n)—квазисигнализирующий оператор для грам-
матик, и участвующая в определении F функция /(Г, D, С) обладает следующим свойством: существует функция g, отображающая
(?U?i)* в натуральный ряд, обращающаяся в нуль на Е* и такая, что для любой грамматики Г и любого вывода D = (cd0, «>ь • •., Вв) в Г имеет место f(T, D, i) = g((»j). Показать, что в этом случае для любой общерекурсивной функции h(n) и любой грамматики Г = = {V, W, /, R), для которой h(n)'^g (/) и L (Г) ф 2?, существует бесконечно много чисел я, удовлетворяющих неравенству FT (п) > h(n).
2.10. а) Показать, что если для класса грамматик существует общерекурсивная функция f(n) такая, что в любой грамматике Ге?Г длины полных выводов цепочек из L(T) длины, не превосходящей п, не превосходят /(л), то для любого квазисигнализирующего оператора Е соответствующий относительный оператор FT является сигнализирующим и для любой грамматики ref функция Fr (п) рекурсивна.
б) Показать, что если для класса грамматик существует общерекурсивная функция f(n) такая, что в любой грамматике Tsf длины цепочек, встречающихся в полных выводах цепочек из ?(Г)
78
СИГНАЛИЗИРУЮЩИЕ ФУНКЦИИ
[ГЛ. 2
длины, не большей п, не превосходят /(я), то для любого квазисигнализирующего оператора F, удовлетворяющего условию упражне-' ния 2.9, соответствующий относительный оператор F* является сигнализирующим и для любой грамматики ГеУ функция Fr (п) рекурсивна.
2.11. Построить грамматику, порождающую множество всевозможных цепочек из [а, Ь}*, являющихся кодами грамматик при способе кодирования, примененном в доказательстве теоремы 2.4.
2.12. Указать способ построения грамматик, порождающих языки из теорем 2.4 и 2.5, по грамматике Г;, порождающей язык 1*1 = {п # f (п) | п = 0,1, ...} в словаре {|, #}, грамматике Г^, порождающей язык L2 = {% (Г) # х # р | F (Г, х) = р) в словаре {а. Ь, |, #}, где v. (Г) и и (дс) — коды грамматики Г и цепочки х (см. доказательство теоремы 2.4) и грамматике Гд, порождающей язык L3 = {а, Ь, |, #}* — L (Г^).
2.13. а) Показать, что при F=S грамматика Г0 из теоремы 2.4 может быть построена так, чтобы имело место неравенство
5ГоМ = max (5! (g («)), kSAsM\ ftS3<gU))),
где g(n) =2n+ f (2") + 1, k — константа и Si(n) = S ,
г i («)
(Гр T2, Гд — грамматики из упражнения 2.12).
б) Получить аналогичную оценку для ТГа(п).
2.14. Найти временнйе и емкостные сигнализирующие машин, построенных при выполнении упражнений 1.16 и 1.17.
2.15. Сформулировать определения временной и емкостной сигнализирующих для Н-машин и ОН-машин (упражнение 1.20). Найти соотношения между сигнализирующими Э-машин, Н-машин и ОН-машин.
2.16. Показать, что если функция Тг(п) примитивно рекурсивна, то и язык ?(Г) примитивно рекурсивен.
ГЛАВА 3
ГРАММАТИКИ СОСТАВЛЯЮЩИХ § 3.1. Деревья выводов
Пусть Г = (К, W, I, R) — НС-грамматика, /) = = (co0, со„) — вывод в Г такой, что [co0[=I, и D' — = (©', ..., соп), ш' = ?.*ф.*г|г, — некоторый соответ-
ствующий D размеченный вывод.
Пусть <о, = рп ... (ри <= V U W). Если ф, -> фг — правило, применяемое на i-м шаге D при разметке, отвечающей D', то фг и фг можно представить (вообще говоря, не единственным образом — см. упражнение 3.2) в виде фi^tiAih, где At <= W, %t, ?ге(К U^)*,
^(Klltt7)*
Фиксировав для каждого i— 1, ..., п— 1 такое представление и обозначая точку рг1 .. • Рг, /_,*р*/*рI, /+!•.. Рikt цепочки со* через Вц, будем говорить, что точка Bi+i./' ‘ цепочки сог+1 является непосредственным потомком точки Bij цепочки щ, и писать у,
если либо а) / = /'<11; |> либо б) />||<|+1, }'= =/-ьI 0i 1—1, либо, наконец, в)/=| h 1+1, 1+ 1</'<
I +1 6» I (т- e. либо Bi+i'i' является «копией» В,-/, либо Bij — точка, заменяемая на г-м шаге, a B;+i,/' принадлежит заменяющему ее отрезку).
Обозначим теперь через М' множество всех точек всех цепочек соо, ..., соп. Ясно, что граф (М-») является деревом. Для а, р е М' будем писать а <( р, если I либо а) а и р являются точками одной и той же цепочки
ио<р, либо б) существуют а', р' е М\ удовлетворяющие условию а) и такие, что из них идут пути в а и в р соответственно. Отношение есть, очевидно, частичный I порядок. Биграф (М<) мы будем называть р а с-
1 тянутым деревом вывода Д
80
ГРАММАТИКИ СОСТАВЛЯЮЩИХ
[ГЛ. 3
При графическом изображении растянутого дерева вывода удобно помещать вхождения, принадлежащие одной цепочке, на горизонтальной прямой, и отношение << понимать как «левее» (ср. § 1.1, стр. 20). Кроме того, договоримся для каждого i располагать цепочку Юг+1 (т. е. соответствующую прямую) ниже цепочки юг. При таком способе изображения можно, не опасаясь h недоразумений, заменить обо-
значения В{1 символами р^-.
Если в {М; -> ) из а в р идет путь ненулевой длины, мы будем называть р потомком а и а — предком р.
Пример. Пусть схема НС-грамматики Г содержит правила А->аВА, ВА^-ВВА, BBB-+BDB, В-+Ъ, bDB^ ->bcdB, М—>6а. Тогда размеченному выводу (*Л*, а*ВА*, аВ*ВА*, а*ВВВ*А, a*B*DBA, a*bDB*A,abcd*B*A, abcd*bA*, abcdba) будет отвечать (в данном случае единственное) растянутое дерево вывода, изображенное на рис. 2.
