Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Мы показали, что класс КС-языков не замкнут относительно операций взятия дополнения и пересечения; было, кроме того, установлено, что не все КС-языки являются детерминированными.
Алгебраическая характеристика КС-языков, доставляемая основной теоремой (п. 15.2.3), объясняет такое положение вещей. Рассмотрим подкласс стандартных КС-языков Dr П Q, где Dr — класс ограниченных языков Дика, a Q — класс стандартных А-языков на некоторой свободной полугруппе. В этих КС-языках все нерегулярности, связанные с замкнутостью или с допустимостью относительно заданного автомата, пропадают. В случае линейных стандартных КС-языков также ясно, что их пересечение (построение которого сводится к образованию пересечения регулярных языков) является линейным стандартным КС-языком. Кроме того, легко видеть, что эти языки являются детерминированными.
Нерегулярности, связанные с общим классом КС-языков, возникают при гомоморфном отображении ф. Вот один из результатов, относящихся к соответствующим алгоритмически неразрешимым проблемам.
Пусть 91* и 93* — свободные полугруппы, ф и ф — гомоморфизмы, отображающие 91* в 93*. Не существует общей процедуры, позволяющей установить, существует ли цепочка / є 91*, такая, что ф(/) = ^(/). Это просто алгебраическая формулировка результата Поста о неразрешимости проблемы соответствий (п. 6.2.3).
Этот результат можно усилить, распространив его на случай, когда ф и ф — мономорфизмы, т. е. когда разные / имеют разные образы. Этот факт объясняет неразрешимость проблемы пересечения.
§ 15.3. совпадение класса кс-языков с классом языков, допускаемых автоматами с магазинной памятью
В главе IX (см. § 9.3) мы доказали, что всякий КС-язык допускается некоторым МП-автоматом. Наметим теперь доказательство обратной теоремы.
15.3.1. Теорема
Всякий язык, допускаемый МП-автоматом, есть КС-язык. Идея доказательства состоит в следующем. Пусть некоторый МП-автомат 91 допускает язык L. Запишем процесс работы автомата 91 в виде цепочки, состоящей из символов, сопоставленных командам автомата, выполняемым на последовательных шагах процесса; обозначим через L' множество всех таких цепочек Нетрудно видеть, что по автомату 91 можно построить односторонний конечный преобразователь, отображающий L' на L (этот преобразователь должен переводить каждый символ команды в читаемый при выполнении этой команды входной символ). Поэтому доста- Г л XV. Дополнительные сведения о КС-языках
245
точно показать, что U есть КС-язык. Но цепочки языка V устроены весьма сходно с цепочками языка Дика (и даже ограниченного языка Дика): команды записи на рабочей ленте соответствуют «левым скобкам», команды чтения на рабочей ленте — «правым»; правда, одной и той же «левой скобке» могут отвечать «правые скобки» различных типов (и обратно), поскольку на входной ленте могут читаться разные символы. Однако можно построить такой односторонний конечный преобразователь т, что прообразы цепочек языка L' относительно осуществляемого им преобразования будут принадлежать некоторому языку Дика D*, и x~l (L') будет пересечением D* с некоторым стандартным А-языком, разрешенные диграммы которого соответствуют, грубо говоря, тем парам команд автомата 91, которые можно выполгять непосредственно друг за другом.
Из этой теоремы немедленно следует другая, о которой мы говорили в п. 9 3.2. Принимая во внимание ее важность, сформулируем ее еще раз.
Теорема. Класс языков, допускаемых (порождаемых) автоматами с магазинной памятью, совпадает с классом контекстно-свободных языков.
15.3.2. Замечание о неоднозначности КС-языков
Рассмотрим гомоморфное отображение ср произвольного стандартного КС-языка Cs на произвольней КС-язык. Язык Cs, цепочкам которого приписывает определению структуру его «естественная» грамматика, однозначен; произвольный КС-язык, который порождается грамматикой, полученной с помощью тройки (D*,Q,(f), где D* — язык Дика и Q — стандартный А-язык, может быть и неоднозначным. Степень неоднозначности цепочки f равна мощности множества ее прообразов относительно ф, т. е.
§ 15.4. упражнения
1. Пусть имеется язык Дика в алфавите {а, Ъ, ...; a',b', ...} и стандартный А-язык, заданный системой уравнений, как описано в п. 14.1.2. Сколькими уравнениями будет задаваться соответ-
степень неоднозначности f = card[ф-1 (f)]-
Стандартный КС-язык
Произвольный КС-язык 246
Часть III. Алгебраический подход
ствующий КС-язык, если воспользоваться для их вывода процедурой, указанной в п. 15.2 3?
2. Стандартный КС-язык называется ограниченным, если он удовлетворяет следующим двум дополнительным условиям:
1°. Для всякого разрешенного перехода от буквы без штриха к другой букве без штриха разрешается переход в обратном направлении между соответствующими штрихованными буквами, и обратно; например, если есть ab, то должно существовать Ь'а', а если есть а'Ь', то должно существовать и Ьа.
2°. Разрешенными переходами типа ху' и х'у могут быть только переходы типа хх', соответственно х'х.
Первый вопрос. Построим матрицу разрешенных переходов, выписывая левые члены диграмм (т. е. строки матрицы) в порядке а, Ь, с, ..., а', Ь', с', ..., а правые (т. е. столбцы) — в порядке а', Ь', с', ..., а, Ь, с, .... В этой матрице естественным об разом выделяется четыре «блока»:
