Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
Формальные свойства грамматик
185
нейио-ограничеиные автоматы, и, кроме того, доказал, что каждый контекстный язык допускается некоторым недетерминированным лииейно-огрзииченным автоматом. Было также указано в работе [4], что дву ленточные автоматы, введенные Рабином и Скоттом [53], соответствуют линейным грамматикам в следующем смысле. Пусть у*— отражение у, а а — заданный символ словаря Vr. Тогда еслн T — двуленточный автомат, допускающий множество пар {(xit у,)} (где Xi, yt — цепочки в словаре Vr—Ixj), то существует линейная грамматика G, порождающая язык [XlCiyi*]-, и обратно, если G есть линейная грамматика, порождающая язык [XtOyi*] (Xi, yt — цепочки в Vt—[а)), то существует двулеиточный автомат, который допускает в точности множество пар ((Jei, у*)}.
Подводя итог всему сказанному, мы видим, что с точки зреиня слабой порождающей способности имеется довольно близкое соответствие между иерархией различных видов грамматик непосредственных составляющих и некоторой иерархией автоматов, а именно общие.системы подстановок соответствуют машинам Тьюринга, контекстные грамматики — недетерминированным линейноограниченным автоматам, бесконтекстные грамматики — недетерминированным автоматам PDS, линейные грамматики — двуленточным автоматам и односторонние линейные грамматики — конечным автоматам.
Курода также показал, что дополнение (по отношению к фиксированному словарю) языка, допускаемого детерминированным линейно-ограниченным автоматом, есть контекстный язык н что каждый бесконтекстный язык допускается некоторым детерминированным линейно-ограничениым автоматом. Отсюда следует, что дополнение бесконтекстного языка есть контекстный язык. Мы увидим ниже (разд. 4.3), что дополнение к бесконтекстному языку не обязательно является бесконтекстным языком и (разд. 4.4) что не существует алгоритма, определяющего, является ли оно бесконтекстным языком или нет.
4.3. Свойства замкнутости относительно операций
Регулярные языки замкнуты относительно булевых операций (т.е. объединения, пересечения н дополнения по отношению к фиксированному алфавиту), а также относительно отражения (т.е. преобразования каждой цепочки av..a„ в иепочку On--Mi), произведения (т.е. образования языка L1-L2= (х1*=^,!/^L1, г ? L2J и бесконечного замыкания (т. е. образования языка U „Ln, где Ln-= L-L- ... -L, п раз). (Cm, разд. 1.2.) Однако это наблюдение лишь частично оправдывается в случае бесконтекстных языков.
Теорема 20. Множество бесконтекстных языков замкнуто относительно операции отражения, произведения, бесконечного замыкания и теоретико-множественного объединения [4 ],
186
Н. Хомский
Ho пересечение двух бесконтекстных языков уже не обязательно является бесконтекстным языком, а следовательно, и дополнение бесконтекстного языка относительно множества цепочек в фиксированном алфавите не обязательно будет бесконтекстным языком.
Теорема 21. Множество бесконтекстных языков не замкнуто относительно операций теоретико-множественною пересечения и дополнения (относительно фиксированного словаря V) 159,,4-J.
Шейнберг [59 ] приводит в качестве контрпримера .йзыки I1= =(а"&"а:7‘) и L2= {ап6?11), каждый нз которых есть бесконтекстный язык, но пересечение которых есть множество пеночек ((TftnO"), не являющееся бесконтекстным языком (пример, приведенный у Бар-Хиллела, Перлса н Шамира [4], в основных чертах совпадает с этим). Пересечение двух множеств может, конечно, быть представлено в терминах объединения и дополнения. Поэтому отсюда следует, что дополнение бесконтекстного языка ие обязательно будет бесконтекстным языком, поскольку объединение бесконтекстных языков бесконтекстно.
Отметим, что языки L1 н L2, определенные в предыдущем абзаце, являются мета-линейными и последовательными языками. Объединение мета-линейпых языков мета-линейио; объединение последовательных языков есть последовательный язык. Следовательно, этот пример в действительности показывает, что множества Xm и з из определения 7 не замкнуты относительно операций пересечения и дополнения, точно так же как и все множество 7, н, кроме того, пересечение двух языков из Xra или двух языков из з не обязательно принадлежит f.
Шюценберже установил (личное сообщение), что этот результат может быть усилен до линейных грамматик (грамматик класса X по определению 7). Рассмотрим грамматику G1 с правилами
S -* аа Sc, S -*¦ bSc, S -»• be (28)
и грамматику G2 с правилами
5 -+ aScc, S ->• aSb, S -»• ab. (29)
Пересечение языков, порождаемых грамматиками G1 и G2, есть множество цепочек (0^6?2'1}, которое не является бесконтекстным языком; но грамматики G1 и G3 линейны. Более того, это грамматики простейшего типа выше уровня конечных автоматов, а именно линейные с единственным нетерминальным символом. Теперь мы Вндим, что даже в этом простейшем случае пересечение порождаемых языков может не быть бесконтекстным, а класс X также не зам-
формальные свойства грамматик
187
кнут относительно пересечения или дополнения (он замкнут относительно объединения).
