Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Пусть &*— свободная полугруппа с базой % = {xit ..., хп) и 33* — свободная полугруппа с базой 33 = {а,Ь, ..., /}. Рассмотрим следующее отображение 91* в (или, быть может, на) 33*: каждое вхождение буквы Xi в цепочках множества 91* заменяется на определенную цепочку /,• из 93*. Такое отображение называется кодированием (а образ цепочки при этом отображении — кодом), если каждая из получаемых цепочек в алфавите 33 допускает только одну интерпретацию (т. е. только одно разложение на образы элементов 91).
Пример. 91 = {1, 2,0}; 93 = [а, Ь}\ 1 ->Ьа 2-* baa 0-*6 1 -*а 2-*аа 0-* b .
— кодирование;
— не кодирование,
поскольку 11 —> аа и 2—*аа.
Теперь ясно, что минимальная линейная грамматика
[S-^flSgl I
S-+c
будет однозначной, если хотя бы одно из двух отображений {t-*fi, і-*gi і 142
Часть II. Некоторые замечательные классы языков
является кодированием. Из определения видно, что вывод любой цепочки в такой грамматике восстанавливается по ней однозначно.
Заметим, что сформулированное условие не является необходимым. Может оказаться, что ни одно из указанных отображений не есть кодирование и тем не менее всякий вывод определяется однозначно.
Пример. Пусть имеется грамматика
S -> aaSa S->bbSb S—>aSbb . S-> b Saa S -> с
Множество цепочек ft, а именно {аа, bb, а, Ь), совпадает с множеством gi и не дает кодирования. Однако грамматика однозначна: достаточно рассмотреть одновременно первую и последнюю букву произвольной цепочки, чтобы однозначно установить, какое правило было применено первым, вторым и т. д. Глава IX
АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ
В § 7.1 главы VII мы показали, что класс рекурсивно перечислимых языков связан с классом машин Тьюринга; однако для описания естественных языков целесообразно рассмотреть языки более частного вида.
Таким более частным классом языков являются, например, контекстно-свободные языки. Они связываются не с самым общим классом комбинаторных систем (эквивалентным классу произвольных машин Тьюринга), а с некоторым весьма специальным классом полутуэвских систем. Имеется и специальный класс автоматов, соответствующий контекстно-свободным языкам. Это так называемые автоматы с магазинной памятью (англ. push-down store automata).
Мы не сможем теперь ограничиваться рассмотрением лишь детерминированных автоматов, как мы поступали до сих пор; начиная с этой главы, слово «автомат» будет использоваться в качестве сокращения для выражения «недетерминированный (точнее, не обязательно детерминированный) автомат».
Строгое доказательство эквивалентности автоматов с магазинной памятью и КС-грамматик можно найти у Хомского [1963] или Гинзбурга [1966, § 2.5]; ср. также § 15.3.
§ 9.1. АВТОМАТЫ, ДОПУСКАЮЩИЕ ЯЗЫКИ
Излагаемая ниже концепция автомата представляет собой формализацию хорошо известного программистам понятия «магазинная память» (англ. push-down stack/store).
9.1.1. Содержательное описание автоматов с магазинной памятью
Автомат с магазинной памятью (сокращенно: МП-автомат) — это система, состоящая из следующих трех компонентов:
1) Входная лента Е, разделенная на ячейки и потенциально неограниченная в обе стороны.
2) Рабочая лента, или лента (магазинной) памяти М, ограниченная с одной стороны (условимся считать, что слева), но потенциально неограниченная с другой; она также разделена на ячейки.
3) Управляющее устройство А, имеющее две головки: • входная головка читает символы на входной ленте Е\ 144
Часть II. Некоторые замечательные классы языков
.. рабочая головка может читать символы на рабочей ленте М, а также производить на ней стирание и запись символов.
Каждая из головок может передвигать свою ленту определенным образом; каким именно, будет уточнено ниже.
Входная лента. До начала работы МП-автомата на входной ленте может быть записана некоторая информация — по одному символу в каждой ячейке. Для записи этой информации используется входной словарь (входной алфавит)
VE = {au а2, ..., ар).
Из соображений удобства к этому словарю присоединяется единичный символ е, имеющий особый статус (см. ниже). В результате мы получаем:
(E) В в % % aU % % В в
А
(M) а 4» А/ В в в
Единичный символ е не следует смешивать с пробелом (пустым символом), который обозначается через В. Цепочки, составленные из символов входного алфавита Ve, записываются на ленте E так, что слева и справа остаются пробелы. Запись осуществляется слева направо.
Рабочая лента. Запись на рабочей ленте осуществляется самим автоматом с помощью рабочего словаря (рабочего алфавита)
Км = Mі, A2, ..., A1
Этот словарь может включать и Ve. К словарю Vm мы присоединим единичный символ е и еще один выделенный символ а, который не используется автоматом в ходе его работы. Получаем словарь
VM-mvMU {О}.
Управляющее устройство. Управляющее устройство способно принимать конечное число внутренних состояний Sо, Su ..., Si, ..., Sj, .,,, Sn. Глава IX. Автомати с магазинной памятью
145
9.1.2. Функционирование МП-автомата
