Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
а) [abode, а\е, bbcd, bf, gde, abc, g};
б) {bab}\]a+;
в) {fg}U[c(rf+-{rf})eg],
ПН. 3. Показать, что язык
а {ее, ccdd}* U {ff, ccda!}* b
является конечно характеризуемым в словаре {а, Ь, с, d, е, f} и не является таковым в словаре {а, Ь, с, d, е, /, g}.
П11. 4. Назовем А - г р а м м а т ико й без омонимии такую А-грамматику, в диаграмме которой никакие две дуги, помеченные одним и тем же символом, не могут, исходить из разных узлов.
а) Показать, что язык, порождаемый А-грамматикой без омонимии, конечно характеризуем.
б) Указать алгоритм, позволяющий для всякой А-грамматики без омонимии Г построить приведенную конфигурационную характеристику языка ?(Г).
[Гладкий 1963(a)],
УПРАЖНЕНИЯ
341
ПП. 5. Указать алгоритм, позволяющий для любой А-грамматики Г с основным словарем V и любых цепочек х, у е У* распознать, имеет ли место х => у.
ЦТ)
ПН. в. Показать, что для любого A-языка L в словаре V, любого (ief и любого г=1, 2, ... множество Кг (b, L) конфигураций ранга г языка L с результирующим b также является А-языком, и при этом по А-грамматике Г, символу Ь и числу г можно построить А-грамматику, порождающую Кг (Ь, L (Г)) [Г ладклй 1964 (а)].
ПН.7. Показать, что в линейном языке
{fg, ае, ad, ag}{J{dmaneg \п = 0, 1, ..от = 1, ..., п + 1} каждая цепочка вида ‘
dk+{~lake (6 = 0, 1, / = 0, 1....k)
является конфигурацией ранга + 1 с результирующим f [Лучкин
1966].
ПП. 8. Указать пример лексически размеченного языка (V, L, Г), в котором ТL г не является укрупнением SL [Успенский 1957].
ПИ. 9. Пусть (V, L, Г) — лексически размеченный язык. Определим на V отношение эквивалентности RL г следующим образом: xRl гу, если существуют xQ, ..., xk е V такие, что xQ = х, xk — у
и для каждого / = 1......k либо xi_xS[xl, либо *г_,Гл:г. (Классы
эквивалентности RL г называются разделами [Успенский 1957].)
а) Всегда ли RL г является L-регулярным укрупнением г?
б) Показать, что если ТL г является укрупнением (ср. упражнение ПП, 8), то /.-производная эквивалентность для RL г совпадает с TL г.
ПП. 10. Показать, что каждое из следующих условий достаточно для однородности лексически размеченного языка:
а) всякий клагс, порожденный семейством, порождается любым семейством, с ним пересекающимся;
б) всякий класс, порожденный семейством, порождается любой окрестностью, с ним пересекающейся;
в) всякий класс, порожденный окрестностью,, порождается любым семейством, с ним пересекающимся;
г) всякий класс, порожденный окрестностью, порождается любой окрестностью, с ним пересекающейся.
ПИ. 11. Является ли достаточным условием однородности лексически размеченного языка попарное непересечение различных классов, порожденных семействами (или порожденных окрестностями, или любых)?
ПН. 12. Пусть (К, L, Г)—лексически размеченный язык. Показать, что:
а) символы х, у е V тогда и только тогда принадлежат одному приведенному классу, когда любой элемент Г(х) азаимозамещаем
342
замещаемость
с некоторым элементом Г (у), и обратно (определение И. И. Ревзина [Ревзин 1967, стр. 159]);
б) непустое подмножество V тогда и только тогда является приведенным классом, когда оно может быть получено из классов, порожденных семействами, с помощью операций пересечения и вычитания, и никакое непустое множество, представимое таким образом, не является его собственной частью.
ПН. 13. Показать, что для любого лексически размеченного языка (V, L, Г):
а) ^-производная эквивалентность для отношения «принадлежать одному приведенному классу» совпадает с TL р [Ревзин 1967, стр. 159]);
б) это отношение является укрупнением Sl тогда и только тогда, когда (V, L, Г) однороден [Ревзин 1967, стр. 160].
БИБЛИОГРАФИЧЕСКИЕ ЗАМЕЧАНИЯ
К главе 1.
Понятие порождающей грамматики введено Н. Хомским [Chomsky 1956, 1957, 1959(a) *), 1963]. (Родственное понятие «полу-туэвской системы» рассматривалось в теории алгоритмов и раньше — см., например, [Юеепе 19521**).) Им же введены понятия НС-грамматики, Б-грамматики и А-грамматики (см. указанные выше работы; Н. Хомский пользуется терминами «грамматики класса 1»для НС-грамматик, «грамматики класса 2» для Б-грамматик и «грамматики класса 3» для A-грамматик). Регулярные выражения введены С. Клини [Kleene 1956].
К главе 2.
Сигнализирующие функции детерминированных вычислений введены в 50-х гг. Г. С. Цейтиным (не опубликовано; см. [Яновская 1959, стр. 44, Трахтенброт 1967, стр. 9]) и независимо
Б. А. Трахтенбротом [Трахтенброт 1956]. Общая теория сигнализи-
рующих функций детерминированных вычислений — перенос ее идей на случай грамматик составляет основную часть содержания § 2.1 — построена М. Блюмом [Blum 1967]. Временная сложность и емкость для грамматик были введены — под влиянием идей Б. А. Трахтен-брота — в [Гладкий 1964(b), 1966]. Понятия левой и правой глубины восходят к работе В. Ингве [Yngve I960], понятие активной емкости — к работам Мэри Кэтрин Интемы [Yntema 1967] и Б. Брейнерда [Brainerd 1967]; в общем виде последнее понятие сформулировано
Э. Д. Стоцким [Стоцккга 1969]. Понятие разброса введено в [Гладкий — Диковский 1970]. Лемма о сцеплении доказана для НС-грам-матик в [Гладкий 1964(b)] и распространена на общий случай в [Book 1969]. Теорема 2.1 доказана для частного случая в [Гладкий
