Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
4.20. Положим Ls, k = {anbalb ... Ьик~1ЬаПЬак+гЬ ... bas\n,
i_l “ 1» 2, ...}, Ls = Lg\ U LS2 (J ... У Lss, L = Li U L2, ... (s, k = 2, 3, k^s). Показать, что:
а) для любого натурального числа s в L, найдется цепочка, имеющая в любой Б-грамматике, порождающей Ls, не менее s различных деревьев вывода;
б) для любого натурального числа s в L найдется цепочка, имеющая в любой Б-грамматике, порождающей L, не менее s различных деревьев вывода.
Замечание. Языки L„ и L не только бесконтекстны, но и линейны (см. ниже, § 5.2).
4.21. а) Показать, что при любом п = 2, 3, ... язык Мп =
п
= U(a/6)* порождается Б-грамматикой с п + 1 вспомогательными г=1
символами и не порождается никакой Б-грамматикой с меньшим числом вспомогательных символов.
Замечание. Легко видеть, что все языки.Мп автоматные.
б) Указать пример A-языка, порождаемого Б-грамматикой с двумя вспомогательными символами и не порождаемого никакой Б-грам-матикой с одним вспомогательным символом.
[Gruska 1967].
4.22. Построить МП-машины, допускающие языки примеров 6, 7, 9,6) из § 1.3 и языки из упражнения 1.15.
4.23. Построить деревья вычислений цепочки а464 в машнне примера 1 из § 4.5 и цепочки a^ajO^a, в машине примера 2 из § 4.5.
4.24. Показать, что для машины примера 3 из § 4.5 ширина деревьев вычисления не ограничена.
4.25. Дополним МП-машину М третьей лентой — назовем ее в ы-
ходной — со своей головкой и своим алфавитом и добавим к ее программе инструкции вида где а —выходной символ; вы-
полнение такой инструкции будем интерпретировать как запись символа а. Полученное устройство М' назовем МП - м а ш и н,о й с выходом.
Если М' сможет, начав работу, когда М находится в начальной лг-ситуации и выходная лента р.-уста, закончить ее, когда М находится в заключительной х-ситуации и на выходной ленте записана цепочка у, то мы скажем, что М'пеоеводитлгв у, и будем писать у = М'(х). Положим: AT (L) = {у | Эх [х е L & у = М' (*)]} (L s V); L0 (AT) = М' (К*).
Показать, что:
а) для любой МП-машины М м >жно построить такую МП-машину с выходом М', что Lo(M') = L(A1);
УПРАЖНЕНИЯ
155
б) для любой МП-машины с выходом ЛГ можно построить такую МП-машину М, что L(M) == L0(M')\
в) для любой Э-машины М можно построить такую Б-грамма-тику Г и такую МП-машину е выходом Mi, что М\(ЦГ)) = L(M).
4.26. Показать, что для любой МП-машины можно построить эквивалентную ей нормальную МП-машину, у которой в любом дереве вычисления непустой цепочки все висячие узлы помечены входными символами (так что в скобочном изображении соответствующей системы составляющих — см. стр. 141—не будет «пустых» пар скобок). Доказать это двумя способами: с помощью теоремы 4.3 (и анализа доказательств лемм 4.12—4.14) и непосредственно (без обращения к грамматикам).
4.27. Доказать теорему 4.8, а) и результат упражнения 4.12 с помощью МП-машйн (т. • е. указать способ построения по МП-ма-шинам Afi и М2 МП-машины, допускающей язык L(Mt) U L(M2), и т. д.).
4.28. Указать алгоритм, позволяющий для произвольной МП-машины М распознать, ограничена ли ширина множества Lc(M), и в случае положительного ответа найти ее верхнюю границу.
4.29. а) Найти для цепочки aabbab еще одно дерево вычисления в машине примера 3 из § 4.5, кроме изображенного на рис. 6.
б) Убедиться, что для любого натурального п найдется допускаемая этой машиной цепочка, имеющая больше п вычислений.
4.30. Показать, что язык {а’пЪпапЪт | т, п = 0, 1, ...} не допускается никакой МП-машиной, рабочий алфавит которой состоит из одного символа. (Такие машины иногда называют счетчик о-в ы м и.)
4.31. Построить детерминированные МП-машины, допускающие:
а) язык примера 7 из § 1.3;
б) «язык бинарных скобочных последовательностей» (порождаемый грамматикой со схемой {/-»-(//),/-»-( )});
в) язык примера 3 из § 4.5;
г) язык [xxbyb()x2b&2X\ \ хи х2, у^{а.....а„}*, Ьф{аи ..., ап}}.
4.32. Показать, что для всякой детерминированной МП-машины можно построить эквивалентную ей детерминированную МП-машину «без зацикливания», т. е. такую, что для любой входной цепочки х этой машины ее (единственное) .«-вычисление заканчивается [Schfit-zenberger 1963, Ginsburg 1966].
4.33. Показать, что класс языков, допускаемых детерминированными МП-машинами, эффективно замкнут относительно: (а) умножения, (б) итерации, (в) подстановки, (г) левого и правого деления на цепочку, (д) взятия дополнения [Ginsburg — Greibach 1966 (b), Ginsburg 1966]. [Указание. Для (д) использовать упражнение
4.32.]
Замечание. Из (д) немедленно следует, что для всякой детерминированной МП-машины М можно построить детерминированную МП-машину, распознающую язык L(M).
4.34. ГТоказать, что следующие языки не допускаются детерминированными МП-машинами:
а) U, L3, ..., где L = {х? I х е {а,, ..., ап}*} (п> 1);
б) L*, где L — то же, что в а);
в) {xxXib&zybQM^ ] хг, у е {аи ..а„}*} («> 1).
156 Б-ГРАММАТИКИ И МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ [ГЛ. 4
Замечание. Сопоставляя упражнения 4.31, г) и 4.34, в}, видим, что класс языков, допускаемых детерминированными МП-маши-нами, не замкнут относительно обращения *).
