Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
Продолжая исследование соотношений между бесконтекстными и регулярными языками, заметим сначала, что существуют бесконтекстные языки, которыв-«ннвкотвром смысле гораздо«болыпе»,>-чем любой регулярный язык.
T е о р е м а 30. Существует бесконтекстная грамматика Gv порождающая L(G) и обладающая следующим свойством: если задан конечный автомат A1, порождающий L(A1)CL(G), то мы можем построить конечный автомат Ai, порождающий L(A1), такой, что: а) L(A1)CL(A^)CL(G) и б) L(A1) содержит бесконечно много цепочек, не принадлежащих L(A1) [491.
Парих показывает, что этот результат имеет место для бесконтекстной грамматики, которая дает соотношения
A" BmAn, A-*cekc, B-^dfkd (т, п, 1). (51)
[В действительности, это также верно для более простой грамматики G, порождающей только L(G)=[a"bman\ т,п>1) (С. Гинзбург, личное сообщение). ] Из теоремы 30 мы видим, что в общем случае мы не можем получить бесконтекстный язык L в качестве
Формальные свойства грамматик
предела возрастающей последовательности регулярных языков, каждый из которых содержит бесконечное число предложений, не входящих в предыдущий член последовательности, и которые все содержатся в L.
Предположим теперь, что мы имеем бесконтекстную грамматику G1 порожда ощую L(G), и конечный преобразователь T с начальным COCTOHHHeMS0. Мы построим новую бесконтекстную грамматику G', которая порождает TlL(G) ]. Предположим сначала, что T ограничен. Тогда мы можем допустить, что он не содержит правил вида
(«, S,)-*-^,*).
Будем строить новую бесконтекстную грамматику G' с выходным словарем преобразователя T в качестве ее терминального словаря и с нетерминальными символами, представленными тройками (Si, IXlSj), TfleSj, Sj—состояния T на ^V1).
Начальным символом в G' является S'. Правила в G' определяются по следующему принципу:
а) S' -*¦ (S0,SjSi) єсть правило в G' для всех ?;
б) если A -S- (X1... (Xi, есть правило в G, то
для всех ?, /, P1...грамматика G' содер-
жит правило
(S1,Л,S;) - (SilIX1, S3l) (Sp1A2lSr,,). . . (Spw AktSjY
в) если (CtlSi) (Sj,x) есть правило в T1
то G' содержит правило (S11 a, Sj) х. (52)
'ЧтобЕг-свхранить условие, что нетерминальные символы суть те и только те, которТЗё"1йябляются в левой части правила мы можем потребовать также, чтобы G' содержала правило
(Si, a, Si) ->¦ (Si, a, Sj) а (53)
для всех а, і, /, не включенных в пункт в).
Терминальные правила в G' представляют собой правила, заданные в пункте в) конструкции (52).
Продолжая вывод из G' до тех пор, пока мы можем обойтись без применения любого терминального правила, мы получим в качестве последней строчки цепочку
*) Нижеследующее построение принадлежит Бар-Хиллелу, Перлсу и Шамиру [4], которые использовали его только для доказательства факта, который здесь мы приводим в качестве теоремы 32, Наша теорема 31 доказывается по существу тем же способом у Гинзбурга и Роуза [21 ]. Это построение тесно связано с представлением преобразователей посредством матриц у Шюценберже (61].
.200
Н. Хомский
(sV “1’ s'i) (sV “2- S'J ¦ • • (?,,' а*« Sik ) а’ (54)
где I0=O1 Vt для всех / и G порождает и,...а*. Кроме того, если G порождает 04...0^(11^ Vt), то для всех I1,...,!*, цепочка (54) представляет собой строчку вывода в G'. Ho выводы с цепочкой (54) в качестве последней строчки будут оканчиваться терминальной цепочкой z тогда и только тогда, когда существуют цепочки X1,...,Xi, такие, что X1...Xk=г и для всех j(aJt S ,J1)-+(Sl^xj) есть предписание в Т, т. е. тогда и только тогда, когда T преобразует входную цепочку «!...а* в z, проходя в процессе этого преобразования через состояния S0lSi1,..., Slk. Таким образом, G порождает язык PIL(G)]. Заметим, что G' может иметь правила вида <х-»-е(гдел:=е в лункте б) конструкции (52)). Однако, как мы видели в разд. 4,правила такого рода не допускают порождения языков, не являющихся бесконтекстными (кроме языка (е)). Следовательно, мы имеем следую-.щий результат, где T — ограниченный преобразователь.
Теорема 31. Если L — бесконтекстная грамматика и T— ,(ограниченный) преобразователь, то T(L)—бесконтекстный язык (или T(L) = Ie)).
Предположим, что R — регулярный язык, допускаемый автоматом F с начальным состоянием S0. Строим преобразователь Т, име-тощий команду (ahSj)->-(Sk, «,) всякий раз, как F имеет предписание (і, /, к), т. е. всякий раз, когда F переходит из состояния Sj в состояние Sk, прочитав вход Qi. Мы моясем предположить, не ограничивая общности, что F является детерминированным (см. теорему 1) и что T ограничен. Пусть G — бесконтекстная грамматика, порождающая L(G). Построим G' при помощи вышеописанной конструкции, но вместо пункта а) в (52) мы имеем единственное правило S'->(S0, S, S0). Теперь легко показать, используя теорему 31, что G' порождает пересечение R с L(G).
T е о р е м а 32. Если R — регулярный язык, a L — бесконтекстный язык, то пересечение LOR есть бесконтекстный язык.
Чтобы избавиться от требования ограниченности преобразовате-.ля T в теореме 31, приведем следующую конструкцию. Если задана бесконтекстная грамматика G, порождающая L(G), заменим сначала каждое правило A-^onl...ак правилом A->qo.1qo.1q...qv.!! д, где q —некоторый новый символ. Теперь применим конструкции (52) и (53), как прежде, чтобы получить G'. Определим теперь язык Q1J следующим образом:
