Гладкий - Формальные грамматики и языки - 1973 (947381), страница 64
Текст из файла (страница 64)
вающихся с выделенным вхождением х, но не содержа.. шихся в нем целиком, то г,аг, ен Е. В русском языке словосочетание важными работами является, по-видимому, конфигурацией ранга 2 с результирующим работами, или шапками, или лекциями и т. п.: 3 а м е ч а н и я. 1) Из определения ясно, что всякая конфигурация ранга г является и конфигурацией любого большего ранга с тем же результирующим.
2) Понятие конфигурации зависит, вообще говоря, от ' словаря, в котором рассматривается язык: при добав- ., лении к словарю новых символов, не входящих в цепоч-, ки языка, могут возникать новые конфигурации (см. уп- . ражнение ПП.З). В дальнейшем мы всегда, если не оговорено противное, будем считать, что язык рассмат- . ривается в своем «наименьшем» словаре, состоящем в точности из тех символов, которые встречаются в его ' цепочках. Если рассматривается одновременно несколь*) Впрочем, при достаточно широком охвате русских предложе- ., ний последние три цепочки не будут гамещаемы на важными работами (ср. ниже, $ П11.
3, пример 2). ко языков, то подразумевается словарь, являющийся объединением соответствующих «наименьших». Будем называть цепочку, принадлежащую языку ~., н е п р и в о д и м о й, если она не содержит вхождений конфигураций этого языка. Множество неприводимых пепочек языка Е будет обозначаться Б(Е). Конфигурацию ранга г языка Е назовем просто й, если она не содержит вхождений конфигураций ранга г (или, что то же самое, рангов, меньших или равных г) этого языка, отличных от нее самой.
Пусть Т вЂ” некоторое множество конфигураций языка Е н Т, — множество всевозможных упорядоченных пар вида (х, а), где х ен Т н а — результирующий конфигурации х. Если Т вЂ” множество всех конфигураций, соответственно всех простых конфигураций, языка 1., то Т1 будет обозначаться К(Е), соответственно П(1.). Упорядоченную пару (Б(Ц, К(Е)), соответственно (Б(Ц, П(Е)), мы будем называть полной, соответственно приведенной, конфигурационной характер и ст и кой языка Е.
Лемм а ПП.2. Пусть Е1, Егы (г'. Если Б(Е1) с= ': — Б(1г) и П(11) ': — К(1г), то Е1 ~ Ег. Доказательство. Пусть хеиЕ1. Индукцией по 1х) покажем, что х я Ег, Если 1х) = 1, то из х ен 1.1 следует х ~ Б(Е1) с= Б(1.2) а Ег Допустим, что для цепочек длины, меньшей п(п ) 1), утверждение доказано н )х~ = п. Если при этом х еи Б(Е1), то х я Б(Ег) с= Ег. Если же х Ф Б(Е1) и г — наименьший ранг конфигураций языка Е1, содержащихся в х, то х содержит и простую конфигурацию тв ранга г языка Е; для некоторых гь г,~ Р и Ь я (г имеем х = ггтвгг и (пг, Ь) я П(Е1).
Поскольку х не содержит конфигураций языка Е рангов, меньших г, получаем г1Ьгген Е1, но 1г1Ьгг1 < п, откуда по индУктивномУ пРедположению г1Ьгг ен Ег и, посколькУ (и2, Ь) я П(1.1) с= К(Ег), х = ггп2гг ~ Ег. Из леммы ПП. 2 непосредственно вытекает Теорем а ПП.1. Пусть Е1, Егеи (Г'. Если Б(Е,) = = Б(Ег) и либо К(Е1) = К(Ег), либо П(Е1) = П(Ег), то Е1 = Ег. Иначе говоря, язык в заданном словаре вполне определяется своей полной или приведенной конфигурацион. ной характеристикой. 11 л. В. Глалкна 322 зАмещлел!Ость 1П.
П 5 п!1.21 злмешлемОсть и ВзхимОзлме!цАемОсть З22 Для лингвистических приложений особо интересным представляется класс языков, у которых Б и П конечны. Такие языки мы будем называть ко н е ч н о х а р а к т ер изу е м ы м и. Кажется в высшей степени правдоподобным, что в естественных языках прн всякои разумном уточнении понятия грамматической правильности все правильные предложения и все конфигурации будут содержать вхождения некоторых словосочетаний стандартного вида («прилагательное+ наречие», «сушествительное+ прилагательное» и т. п.), являющихся простыми конфигурациями, и поэтому естественные языки (точнее — множества правильных предложений естест- 1 ' венных языков) конечно характеризуемы. (В то же время множество всех конфигураций естественного языка, видимо, бесконечно.
Так, в русском языке сочетание сушествительного с любым числом определяющих его прилагательных будет конфигурацией.) Проиллюстрируем нахождение конфигурационных характеристик на примерах. Пример 1. Пусть 1. = (де, аае, аИе, Ьс(ае, ИЬйе, с1, де1, е)е, Щ). Заметим прежде всего, что для произвольного языка и произвольного символа а из его «наименьшего» словаря множество Ф„содержит только такие цепочки, которые входят в цепочки данного языка .':; в качестве подцепочек. Поэтому для конечного языка все Ф„конечны, и, следовательно, К и П (равно как и Б) тоже конечны и могут быть найдены перебором.
Положим Ф,'(1.) =(х~х ~ Ф,(Б) а!х ~ ) 1). Из предшествующего замечания ясно, что если язык Б конечен и символ а входит в какую-либо цепочку языка 1., имеющую наибольшую возможную для цепочек из 1. длину, то Ф,'(1.) пусто. Поэтому в нашем случае Ф( = Фв = Ф,'= Я. Множество Фг также пусто, так как иначе язык Б содержал бы цепочки вида с(ех, где (х~ ) 1. Непосредственно проверяется, что И ~ Ф;; других цепочек Ф,' не содержит, иначе язык Б содержал бы цепочки вида хЬс(е, где ~х~ - 1 и х Ф Ьд. Аналогичным образом легко убедиться, что Ф,'=(де, Я, Ф«=(аа, аИ, Иа, ЬдЬс(, е1). Непосредственно ясно, что цепочки аа, аИ, Иа и ЬдЬс( замешаемы на д и Ьй — на а, а также, что де и 11 не замешаемы на с и е1 — на д.
Итак, Б имеет пять конфигураций 1-го ранга: И, аа, абс(, Ьда, ЬдЬЫ. Далее, де есть конфигурация 2-го ранга с результируюшем с; действительно, из всех цепочек языка Б только в де( имеет. ся вхождение де, не перекрывающееся с вхождениями конфигураций 1-го ранга, и при этом с1 ~ Б. Цепочка е) не является конфигурацией 2-го ранга с результируюшим д, поскольку де1 не содержит вхождений конфигураций 1-го ранга, и все же у1~ 1.. Аналогично' устанавливается, что 11 не есть конфигурация 2-го ранга с результируюшии с. Следующий шаг будет состоять в проверке оставшихся цепочек е1 и 11 на «конфигурационность 3-го ранга»; поступая, как выше, убеждаемся, что е1 является конфигурацией 3-го ранга (с результируюшим д), а 11 — нет.
Наконец, устанавливаем, что 11 не является и конфигурацией 4-го ранга. Итак, имеем Б(1.) =(уе, с1, 111), К(Б) = НИ, а) (аа, у), (аЬй, д), (Ьда, д), (Ьс(Ьс(, д), (де, с), (е1, у)), П(1.) =((Ьд, а), (аа, Аг), (де, с)(ег, й)). Прим е р 2. Пусть 1.'=(Ь"сЬ" (и = О, 1, ...), 1.=а+1.'а+. Легко видеть, что Ф„(1.) = Ч',(1.) = а+, Ф»(Е.) = (Ь), Ф,(1) = '1',(1) = Б'. Поэтому Б (1) = (аса), К Я= =((а'", а) ~ т = 2, 3, ...) () ((х, с) / х ен 1.'), П (Б) = ((аа, а), (ЬСЬ, с)). Дальнейшие примеры см. в упражнениях ПП.2,3,7; см. также ниже пример 3.
Теорем а П11.2. Всякий конечно характеризуемый язык является бесконгенстным. При этом по заданным конечным Б(Б) и П(Б) можно построить Б-грамматику, порождающую Б. Доказательство. Пусть Б — конечно характеризуемый язык в словаре У. Сопоставим каждому а ее У новый символ а и положим Р = (а~а еп У). Для каждой цепочки х =а, ... аы где а„..., ал ~У, Ь ) 1, будем полагать х= а, ... ал, если у =х, будем писать х = у.
Введем еше один символ ТфУ () У и рассмотрим грамматику Г =(У, У()Я, 1, Я! () 112() Яз), где )с! =(1 — » »2!г Е= Б (1 )) Р2 (а — »Х!(Х, а) Ен П(1)) аз (а а!а ~ У). Покажем, что 1. (Г) = Б. 1. Пусть ш = Б(Г). Тогда найдется такой вывод (1= ыа, ны ..., ы„=ш) в Г, что на первом его ОКРЕСТНОСТИ, КЛАССЫ И ТИПЫ 325 <П. И 324 ЗЛМЕШАЕМОСТЪ % п«.з> шаге применяется правило из Й„на всех следующих шагах до /т-го включительно (1 < /т ( п — 1) — правила из /1г и на всех остальных шагах — правила из /1ь. Поскольку й, ен Б(Е) ы Ь и для каждого < = 2, ..., /< цепочка й< получается из й« подстановкой некоторой конфигурации вместо ее результирующего, имеем йл енЕ; но йь = и>. П.
Чтобы показать, что Е~ Ь(Г), достаточно убедиться, что всякая цепочка й ~ Е выводима в Г из !. Но это легко сделать, применив индукцию по <ш~ и воспользовавшись рассуждением, аналогичным примененному в доказательстве леммы ПП.
2. Теорема ПП.2 не может быть обращена. Более того, как показывает следующий пример, даже А-язык может не быть конечно характеризуемым. Пример 3. Пусть Е=(ЬаЬ)()ЬСЬ сЬ(/(а ()сЬ с) ° Ясно, что Ф,(!.) =[а) () сЬ+с, Фь(Ь) =(Ь), Ф,(!.) =(с) (например, в ЬсЬсЬ первое вхождение Ь нельзя заменить ничем, а первое вхождение с можно заменить только цепочкой вида сЬА, но такой цепочкой при /т ) ! нельзя заменить второе вхождение с), Поэтому К(Ь) = =((сЬ "с, а) ( пт = 1, 2, ...),откуда Б (! ) = (ЬаЬ) () а+; все конфигурации здесь, очевидно, простые, так что /1 (Ь), как и Б(Ь), бесконечно. Один частный класс А-грамматик, приводящий к конечно характеризуемым языкам, указан в упражнении ПП. 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
