Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
S-* С SS S-* 1S
s-*v У->Р 184
Часть II. Некоторые замечательные классы языков
2. Построить МП-автомат, допускающий язык, порождаемый грамматикой
S-+TT T-+Та Т-+ЬТ ' T ->с
3. Язык L = {aPbicr\p + <7> г) является КС-языком. Выписать КС-грамматику, порождающую этот язык. Определить, к какому более узкому классу языков ой принадлежит. Построить детерминированный МП-автомат, допускающий этот язык.
4. Проблема. Ниже мы рассмотрим некоторые свойства так называемой бесскобочной записи (записи Лукасевича). Для простоты будем обозначать любой бинарный оператор буквой а, а любой операнд — буквой Ь. Пусть имеется «бесскобочная грамматика» Gp с аксиомой S, терминальными символами а и b и правилами
S->aSS, S->b.
Обозначим через P множество всех терминальных и нетерминальных цепочек, порождаемых грамматикой Gp, и через L — порождаемый ею терминальный язык (таким образом, LczP).
I. Пусть X — цепочка в алфавите {5, а, Ь)\ через а (Я) обозначается длина X относительно буквы а (т. е. число вхождений а в X), через ?(X)—длина X относительно букв b и S.
Положим
Y(X) = a(X)-?(X).
Например, если X = ab3a2S4, то а(Х)=3, ?(X)=7, у(Х) =—4; если У = abazbzabz, то a(F) = 4, ?(F) = 6, y(Y) = -2.
I. 1. Доказать импликацию:
х€ер^ yw=-1.
1.2. Доказать, что если X = RQ, где R и Q не пусты, то
Y (QX- 1-
1.3. Доказать, что верно и обратное: если у(Х) = —1 и для любого непустого начала R цепочки X имеет место неравенство у (R) > О, то X є Р.
1.4. Используя результаты упражнений 1—3, построить детерминированный МП-автомат М, допускающий язык L.
1.5. МП-автомат называется неуправляемым, если все его команды имеют вид (a, Si, e)->(Sjt х). Может ли автомат M быть неуправляемым? Какова была бы —в случае положительного ответа на этот вопрос — роль рабочей ленты? Глава IX. Автомати с магазинной памятью
155
II. Исследуем теперь структуры, которые Gp сопоставляет цепочкам языка L.
II. 1. Объяснить, как можно построить дерево вывода цепочки языка L.
Построить дерево вывода цепочки a3babzababzab2. Доказать, что грамматика Gp однозначна.
II. 2. Можно ли построить МП-автомат Т, снабженный, кроме входной и рабочей ленты, еще одной лентой — выходной и преобразующей бесскобочную запись в скобочную? Это означает, что любой входной цепочке f є L автомат T ставит в соответствие (записывая на выходной ленте) цепочку T(f)—«перевод» цепочки / в скобочную запись:
abb переходит в (bab), aabbb переходит в {(bab)ab) и т. п.
III. 1. Обозначим через pi произвольное целое число, большее единицы, и через k — некоторое фиксированное целое положительное число. Доказать, что для любого данного k существует бесконечно много цепочек языка L, имеющих вид
ар'ЬршЧр2 ... аЩЩ.
III. 2. Исходя из этого результата, доказать, что язык L не может быть порожден никакой металинейной грамматикой.
§ 9.4. ПРИЛОЖЕНИЯ КС-ЯЗЫКОВ
Выше было сказано, что КС-языки совпадают с языками, допускаемыми (порождаемыми) автоматами с магазинной памятью; с другой стороны, отмечалось также значение магазинной памяти для программирования. Тем самым устанавливается определенная связь между КС-языками и проблемами программирования для электронных вычислительных машин. Поэтому целесообразно вкратце охарактеризовать приложения КС-языков в программировании и более широко — в области автоматической обработки информации.
9.4.1. Примеры приложений
Важная роль КС-языков объясняется, по всей вероятности, следующими их особенностями:
— в КС-языках возможно неограниченное (циклическое) вставление цепочек друг в друга;
— методы порождения КС-языков весьма естественны с интуитивной точки зрения;
— алгоритмы распознавания КС-языков достаточно просты.
К КС-языкам пришли независимо многие исследователи, работавшие в области формализации синтаксиса: 156
Часть II. Некоторые замечательные классы языков
1) Так называемая нормальная форма Бэкуса
(Л):: = (S), (С) I п (D)
представляет собой по существу вариант записи правил КС-грамматики; соответствующая КС-грамматика имеет следующий вид:
A ^ ВС, A-»nD,
где Л, В, С, D^Va, п є Vt.
2) В лингвистике: модель непосредственно составляющих Р. Уэллза и 3. Хэрриса, а также категориальные грамматики И. Бар-Хиллела оказались эквивалентными КС-грамматикам1).
3) В автоматическом переводе: почти все грамматики, созданные для целей автоматического перевода, оказались КС-грамматиками.
4) Большинство языков программирования таково, что их синтаксис может быть описан посредством КС-грамматик.
9.4.2. Алгол
Помимо арифметических выражений, в Алголе есть и другие фрагменты, где возможно самовставление. Из них мы укажем здесь два.
а) Возможны выводы вида
(непомеченный составной оператор) #
=Ф (начало)" (непомеченный составной оператор) (конец)".
Таким образом, алгольная программа, имеющая п символов начало в начале и п символов конец в конце, считается синтаксически правильной (причем совпадение числа символов начало и конец существенно для правильности).
