Главная Промышленная автоматика.

*2.1.11. Покажите, что каждое рекурсивно перечислимое множество может порождаться грамматикой, использующей не более двух нетерминальных символов. Может ли произвольное рекурсивно перечислимое множество порождаться грамматикой, использующей только один нетерминальный символ?

2.1.12. Покажите, что если грамматика G = (N, Я, 5) такова, что 4i=N = /i и S не содержит символов Л, Л, ...,то существует эквивалентная ей грамматика G(N, S, Я , Л), у которой N = {Aj, Лз, Л„}.

2.1.13. Докажите, что грамматика из примера 2.1 порождает язык {0"1" I Указание: Обратите внимание, что каждая выводимая цепочка содержит не более одного нетерминала. Таким образом, правила можно применять только в одном месте цепочки.

Определение. В грамматике без ограничений G данную цепочку можно вывести многими способами, которые по существу одинаковы и отличаются лишь порядком, в котором применяются правила. Если грамматика G контекстно-свободная, то эти по существу одинаковые выводы можно представить с помощью одного дерева вывода. Однако если грамматика G контекстно-зависимая или без ограничений, то классы эквивалентных выводов можно определить следующим образом.

Пусть G = (N, 2, Я, S) -грамматика без ограничений. Пусть £) множество всех выводов вида S=w, т. е. элементами множества Услужат такие последовательности вида («о, а,... что a = S, сх„€2* и a/ i=>a,-, 1<(<«.

Определим отношение на множестве D, положив

К, а„ сс„)о(Ро> Pi, Р.) тогда н только тогда, когда найдется такой индекс / между 1 и я-1, что

(1) aj = j для всех ji;

(2) можно писать (г-гУгУУзУУь и f+iyiysy, причем в Я есть правила у~Ь и у-е, и либо = Vi6V3V4V5 и

= Vi72T3eV5. ибо наоборот.

Пусть i? -наименьшее отношение эквивалентности, содержащее Rq. Каждый класс эквивалентности отношения R образован по существу одинаковыми выводами данной цепочки.

**2.1.14. Каков максимальный объем класса эквивалентности отношения R (как функция от п и если грамматика G

(а) праволинейная?

(б) контекстно-свободная?

(в) такова, что каждое ее правило имеет вид а-и сс<р1?

*2.1.15. Пусть G определяется правилами

SAOB\B\A А-ВВ\0 В-АА I 1

Каков объем класса эквивалентности отношениясодержащего вывод S>AOB=BB0B=y\BOBAAAOB=>\OAOB=\OO0B\0OO\?

Определение. Грамматика G называется однозначной, если каждая цепочка w из L (G) появляется в качестве последней компоненты вывода в одном и только в одном классе эквивалентности определенного выше отношения R.

Например, грамматика

SabC\aB Bbc bC-bc

неоднозначная, так как последовательности (5, аЬС, abc) и (S, аВ, abc) принадлежат двум различным классам эквивалентности.

*2.1.16. Покажите, что каждый праволинейный язык определяется однозначной праволинейной грамматикой.

*2.1.17. Пусть G = (N, 2, Я, 5) -КЗ-грамматика и NljX содержит т элементов. Пусть оу-слово из языка Л (G). Покажите, что 5=4> W, где я<(/п+1)!1.

2.1.18. Покажите, что каждый КЗ-язык рекурсивен. Указание: С помощью результата упр. 2.Ы7 постройте алгоритм, определяющий для произвольного слова w и КЗ-грамматики G, принадлежит ли W языку L (G).

2.1.19. Покажите, что каждый КС-язык рекурсивен. Указание: Используйте упр. 2.1.18, но обратите внимание на пустое слово.

*2.1.20. Покажите, что если G = (N, 1, Я, 5) -грамматика без ограничений, то существует такая КЗ-грамматика G = (N, 2[]{с}, P,S), что wL{G) тогда и только тогда, когда mL(G) для некоторого tO. Указание: Дополните каждое не контекстно-зависимое правило грамматики G буквами с. Затем добавьте правила, позволяющие буквам с сдвигаться к правому концу любой выводимой цепочки.

2.1.21. Покажите, что если L = L (G) для произвольной грамматики G, то существуют такой КЗ-язык и такой гомоморфизм h, что L~h{L).



2,1.22. Пусть {Лд, Лз, ...} -счетное множество нетерминальных символов, не содержащее символы О и 1. Покажите, что каждый КЗ-язык IsjO, 1}* имеет КЗ-грамматику G = (N, {0,1}, р, Aj), в которой К--{Л1, Л, Л,-} для некоторого 1. Мы будем называть такую КЗ-грамматику нормализованной.

*2.1.23. Покажите, что множество определенных выше нормализованных КЗ-грамматик счетно.

*2.1.24. Покажите, что существует рекурсивное множество, содержащееся в {О, 1}*, которое не является КЗ-языком. Указание: Упорядочите нормализованные КЗ-грамматики, чтобы можно было говорить об i-й грамматике. Аналогично задайте лексикографический порядок на множестве {О, 1}*, чтобы можно было говорить об i-u цепочке в {О, I}*. Затем определите L = {Wi\wifL(Gi)} и покажите, что язык L рекурсивный, но не контекстно-зависимый.

**2.1.25. Покажите, что язык определяется грамматикой тогда и только тогда, когда он распознается машиной Тьюринга (машина Тьюринга определена в упражнениях разд. 0.4).

2.1.26. Определите недетерминированный распознаватель, памятью которого является первоначально пустая лента машины Тьюринга, причем ее длина не должна становиться больше длины входной цепочки. Покажите, что язык определяется таким распознавателем тогда и только тогда, когда он контекстно-зависимый. Этот распознаватель называется линейно ограниченным автоматом (сокращенно ЛО-автоматом).

Определение. Индексная грамматика - это пятерка G = = (N, 2, Д, р, S), где N, 2 н Д-конечные множества нетерминалов, терминалов и посредников соответственно, SN-na-чальный символ, р - конечное множество правил вида

AX,W,X,W, ... ХД„ (п>0)

Af~.X,Y,X,Y, ... (п>0)

где Л€N, X/CNU2. /Д и iA*, причем, если то

Wi = e. Пусть а и р-цепочки из множества (NA*u2)*, Л N, 9€Д*, и пусть AXjj ... Х„„ принадлежит Р. Тогда мы пишем

аАЩ>ааХ,Ч\[Х,,% ... ХДЛР

где -9, если X,-€N, и ] = е, если Xi2. Таким образом, цепочка посредников, следующая за нетерминалом в левой части правила, распределяется по нетерминалам правой части,

НО не по терминалам, за которыми никогда не могут идти посредники. Если Af-Xi ... ХД„ принадлежит Я, то

aAfe=oOX,fi[ ... XWM

где Щ определяются так же, как и выше. Этот шаг „поглощает" посредника, следующего за Л, а в остальном он такой же, как и шаг первого типа. Пусть обозначает рефлексивное и

транзитивное замыкание отношения и пусть, наконец,

L(G)=r{w\w* и 5=j>Jay}

Пример 2.7. Пусть </ = ({5, Т, Л, В, С}, {а, Ь, с}, {f, g]. Я, 5).

где Я состоит из правил

5-Г-Г-Л!-Bf-Cf-

Bg-Cg

• ABC

cC

Тогда i(G) = {a«b"crt> 1}. Например, цепочка алйЬсс имеет вывод

STg =Tfg

AfgBfgCfg >aAgBfgCfg :=aaBfgCfg aabBgCfg =Ф aabbCfg =Ф aabbcCg =Ф aabbcc П

*2.1.27. Постройте индексные грамматики для языков (а) {ш£}\т{а, Ь}*},

(б) {а"Ь" \п- 1}.

**2.1.28. Покажите, что каждый индексный язык контекстно-зависимый.

2.1.29. Покажите, что каждый КС-язык индексный.

2.1.30. Давайте постулируем распознаватель, память которого представляет собой одно целое иеотрнцательное число (записанное, если хотите, в двоичной форме). Предположим, что управляющими цепочками, описанными в разд, 2.1.4, являются



только X н у. Какие нз следующих функций могут быть функциями доступа к памяти для этого распознавателя?

(а) / О")

/ О, если i четно, 1 1, если i нечетно.

(б) f (г) = I четно,

(в) f(i)

если i нечетно.

О, если i четно и под входной головкой

находится входной символ а, 1 в противном случае.

2.1,31. Какие из следующих функций Могут быть функциями преобразования памяти для распознавателя из упр 2 1 30

(а) g(i, Х) = {), J у. . . .

gO\ y)-~-irl.

(б) g(i, X)Q,

М-], если предыдущая управляющая

цепочка была X. / + 2, если предыдущая управляющая

цепочка была К.

Определение. ТАГ-система состоит из двух конечных алфавитов N и 2 и конечного множества правил вида (а, р),, где а, P$(Nu2)*. Если 7 -произвольная цепочка из (Nu2)* и (ос, р) - правило, то мы пишел! ayj -ур, т. е. префикс с. в начале любой цепочки можно стереть при условии, что потом в конце цепочки будет приписано р. Пусть -* -рефлексивное и транзитивное замыкание отношения Для любой цепочки y(Nu2)* обозначим через Ly язык {w\w2* и у1-

**2.1.32. Покажите, что Ly всегда можно определить некоторой грамматикой. УА;й:.э/7иг/; Используйте упр. 2.1.25 или посмотрите [Минский, 1967].

**2.1.33. Покажите, что для любой грамматики G язык L(Cj) можно определить ТАГ-системой описанным выше способом. См. указание к упр. 2.1.32.

Открытые проблемы

2.1.34. Является ли дополнение любого контекстно-зависимого языка контекстно-зависимым?

ПпгЛ определено, обычно называют канонической системой

Поста [е нормальной форме). ТАГ-система должна удовлетворять еще иеко торым дополнительным условиям (см. [Минский, mi]).-Прим. nepfe.

ЗАМЕЧАНИЯ ПО ЛИТЕРАТУРЕ

Если распознаватель из упр. 2.1.26 детерминированный, то он называется детерминированным линейно ограниченным (ДЛО) автоматом.

2.1.35. Распознается ли любой КЗ-язык ДЛО-автоматом?

2.1.36. Распознается ли любой индексный язык ДЛО-автоматом?

Из упр. 2.1.28 следует, что утвердительный ответ в упр. 2.1.35 влечет утвердительный ответ в упр. 2.1.36.

Замечания по литературе

Теория формальных языков была в значительной степени стимулирована работами Хомского в конце 1950-х годов [Хомский, 1956, 1957, 1959а, 19596]. Хорошими примерами ранних работ по порождаюш,им системам служат [Хомский, 1903] и [Бяр-Хиллел, 1964].

Иерархия Хомского грамматик и языков хорошо изучена. Многие из основных результатов, касающихся иерархии Хомского, приведены в упражнениях. Большинство из них доказаны в книгах Хопкрофта и Ульмана 119G9] н С. Гинзбурга [1906].

С тех пор как Хомский ввел грамматики составляющих, в литературе появились многие другяе модели грамматик. В некоторых из ннх используются специальные виды правил. В качестве примеров таких грамматик назовем индексные грамматики [Ахо, 1968], макрограмматикн [Фишер, 1968] и грамматики с рассеянным контекстом [Грейбах и Хопкрофт, 1969]. В другнх грамматических моделях налагаются ограничения на порядок применения прйБил, например в программных грамматиках [Розенкранц, 1958]).

Распознавателн для языков тоже изучались очень широко. Машины Тьюринга были введены А. Тьюрингом в 1936 г. Несколько позже в работе Мак-Каллока н Питтса [1943] появилось понятие конечного автомата. Изучение распознавателей было стимулировано работами Мура [1956], Рабина н Скотта [1959] 2).

В теории языков значительные усилия были приложены для выяснения алгебраических свойств классов языков н для получения результатов, связанных с проблемой разрешимости для разных классов грамматик н распознавателей. Для каждого из четырех классов грамматик в иерархии Хомского существует класс распознавателей, определяющий в точности те языки, которые порождаются грамматиками этого класса. Эти наблюдения привели к изучению абстрактных семейств языков и распознавателей, причем классы языков определяются в терминах их алгебраических свойств. Определенные алгебраические свойства класса языков оказываются необходимыми и достаточными для сутцестпования соответствующего класса распознавателей для этих языков. Работа в этой области была начата Гинзбургом н Грейбах ]1969] и Хопкроф-том и Ульманом [1967]. Хороший обзор теории языков к J970 г. дан Буком [1970].

Хейнс [1970] утверждает, что левоконтекстные грамматики из упр. 2.1.6 порождают в точности контекстно-зависимые языки*). Упр. 2.1.28 взято нз [Ахо, 1968].

А также в матричных грамматиках Абрахама [1965].- Прим. перев. ) Следовало бы упомянуть здесь и работу Клини [1956].- Прим. перев. ) Доказательство этого утверждения см. в § 3.5 книги Гладкого [1973].- При.ч. перев.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 [19] 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.002