Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
а) Показать, что классы ОА-языков и, ОБ-языков эффективно замкнуты относительно преобразований, осуществляемых конечными автоматами с выходом.
б) Верно ли это для классов линейных, металинейных, итерационно-линейных и ОБ-ОАЕВ-языков?
5.10. Указать способ построения по диаграмме ОА-грамматики Г с основным словарем V диаграммы ОА-грамматики, порождающей язык Пр2МГ), % — У-
5.11. Показать, что класс ОА-языков эффективно замкнут относительно обращения. (Определение см. в сноске на стр. 156).
5.12. Показать, что классы линейных, металинейных, итерацион-но-линейных и ОБ-ОАЕВ-языков эффективно замкнуты относительно пересечения с ОА-языками и относительно подстановки ОА-языков.'
УПРАЖНЕНИЯ
181
5.13. Множество натуральных чисел Е (или, что то же самое, язык в словаре {|}, см. стр. 34) называется периодическим, если существуют такие k, I, что при п > k из п е Е следует п + / е Е. Показать, что множество натуральных чисел является периодическим тогда и только тогда, когда оно есть ОА-язык, причем по наименьшим соответствующим k и I можно построить нужную ОА-грамматику, и обратно, по такой грамматике можно найти наименьшие k и I.
5.14. а) Указать алгоритм, позволяющий для любой ОА-грам-
матики (V, W, I, R) и любого множества распознать, суще-
ствует ли такая цепочка х е V*, что О = 0(х) (см. доказательство теоремы 5.7).
б) Указать алгоритм, позволяющий для любой ОА-грамматики (V, W, /, R) и любых цепочек x,y,zs V* распознать, переводит ли г класс 0(х) в класс О (у).
5.15. Будем говорить, что отношение эквивалентности ~ на V*, где V — словарь, совместимо с конкатенацией справа, если для любых х, у, г е V* из х ~ у следует хг ~ уг. Показать, что:
а) Если для произвольной ОА-грамматики Г = (V, W, I, R) определить отношение ~ на V* следующим образом: х ~ у тогда и только тогда, когда П(х) = П(у), где П(и) означает множество тех Ле?, которые являются концами путей, начинающихся в / и производящих и, то ~ есть эквивалентность, согласованная с L(T) и совместимая с конкатенацией справа.
б) Для того чтобы язык L в словаре V был ОА-языком, необходимо и достаточно, чтобы существовала согласованная с t и совместимая с конкатенацией справа эквивалентность конечного индекса на V*.
в) Для того чтобы язык L в словаре V был ОА-языком, необходимо и достаточно, чтобы отношение R, определяемое следующим образом:
xRy = (Vz е К*) [xz s L = уг s L],
имело конечный индекс.
5.16. Показать, что следующие линейные языки не являются автоматными: {х? | х s F+}; {хс% | х s У+) (в обоих случаях мощность V ^ 2); язык примера 12 из § 1.3.
5.17. а) Доказать следствие из теоремы 5.5 непосредственно, т. е. указать способ построения по Б (ОБ)-грамматике Г] и А (ОА)-грамматике Г2 такой Б (ОБ) -грамматики Г, что L (Г) = L (Г,) П L (Г2). Показать, что если при этом Г] однозначна, то и Г можно сделать однозначной.
б) Показать, что Б-язык
{х I х е {а, 6, с, d}*; | х \а “ | л: \b V | х \с = [ л: \а] неоднозначен.
5.18. Для того чтобы каждому дереву вывода в ОБ-грамма-тике Г отвечало единственное растянутое дерево вывода, необходимо и достаточно, чтобы Г была линейной. Доказать.
5.19. Показать, что для всякой линейной ОБ-грамматики можно построить эквивалентную ей линейную ОБ-грамматику, все правила
182 СПЕЦИАЛЬНЫЕ КЛАССЫ БЕСКОНТЕКСТНЫХ ЯЗЫКОВ [ГЛ. 8
которой имеют вид А -*? аВ, А -*? Ва или А-*- А, где А, В — вспомогательные символы, а — основной символ.
5.20. Определим диаграмму линейной ОБ-грамматики Г = = (V,W,I,R) с правилами вида, указанного в упражнении 5.19, следующим образом [Диковский 1970]: узлами диаграммы будут элементы ИР; если A-voBeJ?, то из Л в В идет дуга, помеченная парой (а, А); если А Ва s R, то из А в В идет дуга, помеченная парой (A, а); I — начальный узел; если A-+A^R, то А — заключительный узел. Полный путь определяется так же, как для диаграммы ОА-грамматики.
а) Определить цепочку, производимую путем в диаграмме, так, чтобы множество цепочек, производимых полными путями, совпало с ЦТ).
б) Обобщить понятие диаграммы на случай произвольной линейной ОБ-грамматики.
5.21. а) Назовем двуленточным конечным автоматом (ДК-а втоматом) машину Тьюринга с двумя лентами Л\ и Л2, каждая из которых имеет свою головку, общим для обеих лент алфавитом, инструкциями только типа (i) (стр. 42) и множеством состояний, разбитым на два непересекающихся подмножества Qi и Q2 так, что инструкция, имеющая в левой части состояние из Q, (/= 1, 2), выполняется на ленте Л г- ДК-автомат допускает пару цепочек (х,у), если при записанных на и Л2 цепочках х и у соответственно автомат может, начав вычисление в начальном состоянии с головками, обозревающими левые граничные маркеры, закончить его в заключительном состоянии с головками, обозревающими правые граничные маркеры. Язык, допускаемый ДК-а втоматом М (обозначение: L(M)), есть множество допускаемых им пар цепочек. ДК-автомат М и грамматика Г эквивалентны, если L (Г) = = {xQ | (х, у) е L (М)}. Показать, что для всякого ДК-автомата можно построить эквивалентную ему линейную ОБ-грамматику и обратно [Rosenberg 1967].
