Гладкий - Формальные грамматики и языки - 1973 (947381), страница 5
Текст из файла (страница 5)
усть зь ..., $д — абстрактнь1е символы и Вь ... ...,Вр — языки (точнее, символы, обозначающие языки). Выражение, составленное из $, ..., ~, В, ..., В „с помощью знаков объединения и умножения *), соответственно знаков объединения, умнож ции, называется многочленом, соответственно регулярным выражением от $ь ...ДА с коэфф и ц и е н т а м и Вь ..., Вр. Если интерпретировать мьо $ь ..., $А КаК ПЕРЕМЕННЫЕ, ПрОбЕГаЮщИЕ КаКИ - б 1 жества языков, то многочлен (регулярное выражение) становится функцией от этих переменных; значение этой функции, получаемое при подстановке на место переменных $ь ..., еь конкретных языков (.ь ...,1,А, есть также некоторый язык; мы будем говорить, что этот язык представляется (или задается) данным мнагочленом (регулярным выражением) п и — Ь, ...
=Е. 1 ..., $А = д. Например, язык, состоящий из всевозможных цепочек в словаре (а, 6), содержащих вхождение фиксированной цепочки ы, задается регулярным выражением ФЯ) = (а, 6)'Яа, 6)* при $ = (ы). Многочлен (регуляриое выражение), не содержащий (не содержащее) переменных, называется з а м к н у*) Знаком умноження можно считать пробел.меж б ду укиями. ГРАММАТИКИ % !.я! т ы м; замкнутый многочлен (регулярное выражение) представляет единственный язык.
Два многочлена (регулярных выражения) от переменных $ь ..., $А тождественны (или тождес т в е н н о р а в н ы), если они отвечают одной и той же функции, т. е. Нри любой подстановке языков вместо переменных представляют один н тот же язык. В силу упомянутого выше дистрибутивного закона любой многочлен от $» ..., ~А тождественно равен некоторому многочлену вида Опт, ... а», где ан, ... 1 /=1 ..., ам — переменные нлн коэффициенты.
й !.2. Грамматики В самом широком смысле формальными грамматиками, или просто грамматиками, называют любые «автоматические устройства» (т. е. исчисления или алгоритмы), позволяющие «задавать» языки. При этом «задание» может осуществляться по-разному: оно означает либо возможность для каждой цепочки данного языка подобрать такой режим работы устройства, чтобы к концу работы получить («породить») эту цепочку (причем, разумеется, ни одна цепочка, не принадлежащая языку, не должна «порождаться»), либо возможность «перечислить» язык, т.
е. организовать работу устройства так, чтобы оно выдавало цепочки языка одну за другой и могло бы выдать любую из них, работая достаточно долго, либо, наконец, возможность для произвольной цепочки (в соответствующем словаре) получить от устройства ответ на вопрос, принадлежит ли эта цепочка языку. Из трех указанных подходов мы выберем первый. Как станет нам ясно впоследствии (а читателю, достаточно хорошо знающему теорию алгоритмов, должно быть ясна уже сейчас), это не сужает класса описываемых языков — любой язык, допускаю.
щий задание первым способом, допускает также задание вторым нли третьим, В то же время именно такой подход лучше всего моделирует ситуацию, имеющую место при пользовании языком (естественным или 27 грамматики основныв понятия 4 ь21 искусственнь1м) *) — основная задача там рождении предложен б лом. Правда, эта ситуация мо е д ным смысмоделируется далеко не е е — в модели происхо ит р дит порождение не с заданным смыслом, а лю ных предложени" ( й (понятие смысла в эт ' , а любых правиль- образуется в текст, поскольк которь'х о~ущ~~~~~яе~ся переход от ' И так, мы останавливаемся на понимании г амм частности, возможны такие которых все возникающие в п промежуточные объек б кты удут тоже цепочками, кие, при которых эти объекты ми, и та- ду.
Нас здесь будут интересовать ис могут иметь ин п н вать нсклнэчительно снов ., никакому д гом во посо у ); в то же время он обладает тем ») Вэтойипеы разных значениях (см. введение, . 14 1б). р д душей фразах слово «язык» ° «2 Нля ие, стр. 4 — 15). ) Для более точного моделирования пе ехо а тексту более адекватны как ра ания перехода от смысла к межуточные объекты и ею бо лаются деревьями (см.
12 лад й — М р 1р таких грамматик еще недоста ]). днако теория ста р р отава, ао эс ком слустаточно аз аб есь наи олее важно — теория «д матик не может не опираться п о е щ устроенных «цепочечиых» граммати аться существенным об азом ~~ж~мщ которые и являются »»»2 игн. ) аэумеется, это утверждение не носит ха ческой .теоремы.
Его статус б е носит характера математис удет разъяснен в конце $ 1.4, преимуществом, что по крайней мере для наиболее важных частных случаев позволяет сопоставлять порождаемым предложениям весьма естественные описания их структуры (см. ниже, $' 3.1). Еще одно весьма важное достоинство данного способа состоит в том, что он хорошо вписывается в некоторую более общую систему понятий математической логики, теории алгоритмов и теории автоматов ').
Итак, мы переходим к определению порождающих грамматик в смысле Н. Хомского; до тех пор, пока не будут введены в рассмотрение другие типы грамматик, — а по большей части и после этого (когда невозможно недоразумение) — мы будем в качестве синонима для выражения «порождающая грамматика» употреблять просто слово «грамматнка». (Порождающая) грамматика — это упорядоченная четверка Г = ()г, Ф', 1, й), где: 1) )г и 2) )й' — непересекающиеся, непустые конечные множества; 3) 1 — некоторый элемент Ф'; 4) )с — конечное множество цепочек вида ~р- ф, где ф и ф — различные цепочки в словаре )г [) [э' и — — символ, не входящий в )г [) Ф'. Множества )г и )р' называются соответственно ос новным н вспомогательным словарями (алф а в и т а м и) грамматики Г, а их элементы — соответственно основными и вспо м огательн ь1 м и символам и Г**); 1 называется начальным с имволом Г, Р— схемой Г и элементы )1 — яр а в ил ам и Г.
Цепочки ф и 2р называются соответственно левой и пр а вой частями правила ф — ф. Объединение )г0 [й' мы будем иногда называть п о л и ы м слова рем грамматики Г. Пусть г = ср- ф — правило грамматики Г и ~, е<ре$2 — вхождение ~р в цепочку ш = $2грйэ в словаре )г [) В'. В этом случае мы будем говорить, что цепочка ') Заметим, что эта система понятий возникла еще до исследований Н.
Хомского, и то обстоятельство, что его концепция сразу нашла готовую формальную базу, очень сильно способствовало успешному развитию этой концепции. Таким образом, и здесь теория опередила потребности приложений, как бывает чаще всего, вопреки распространенному среди «широкой публики» ходячему мнению. *') Вместо слов «основной» и «вспомогательный» нередко употребляются соответственно слова терминальный н нетармннвльный, Гплммлтики й ьг1 основныи понятия (гл. 1 т) = $ггр$г получается из ш применением правила г к вхождению йг» ~р» йг цепочки ~р. Если цепочка т) получается из цепочки ю применением какого-либо правила . Г, будем говорить, что т) непосредственно выводима и з ю в Г, и писать ш[= т) или просто а[= т).
Последовательность цепочек 0 = (юо, шь ., ю,) ' (п ) 1) называется в ы в о д о м ю„из юо в грамматике Г, если для каждого (, 1 ( 1 ( и, имеет место о»;-г~ соь Число п называется длиной вывода О.. Если существует вывод т) из ш в Г, то мы будем гово- ' рить, что т) выводима из ш в Г, и писать ю) — т) или т). Вывод (юо, юь ..., шя) называется полным, если шо = 1 и ю — цепочка в словаре у'. Если О = (шо, юь ..., ш,) — вывод в грамматике Г и для некоторого ( = 1, ..., и цепочка нн получается из шг, применением правила р - ф к вхождению йг»~ряЧг цепочки «р в ен ь то мы будем говорить, что это правило применяется на 1-м шаге вывода 0 к вхождению йгн~рнт)г н что данное вхождение ~р в ш заменяется на (м шаге вывода О. Размеченн ы м в ы в о д о м, соответствующим выводу О, мы будем называть последовательность(ю', ш'„..., ю„' и ш„), где со', (г =О, ..., а — !) — вхождение, заменяемое на 1-м шаге вывода О. Одному выводу может, вообще говоря, соответствовать много размеченных выводов (см.
упражнение 1.9). Множество цепочек в основном словаре грамматики Г, выводимых из ее начального символа (иначе — множество последних цепочек всевозможных полных выводов в Г), называется языком, порождаемым г р а м м а тико й Г, и обрзначается 0(Г). Из сформулированных определений видно, что существенным свойством процесса работы порождающей грамматики является его недетерминированностти если оборвать вывод на какам-либо шаге, то продолжение, вообще говоря, не восстанавливается однозначно по оставшейся части н может быть выполнено разными способами. Таким образом, грамматика — это исчисление, т. е, разрешение производить некоторые операции [Марков 1954, стр. 203] — в данном случае подстановки в цепочки одних подцепочек вместо других (а не алго.
е. не предписание производить какие-то операП ример. Пусть Г = ((а, Ь, с), (А, В, С, О), (А- ВСА, ВСВ- О, ВС- Ьс, ОС- а, сА-~.с, аА -» а)). Пример полного вывода в Г: (А, ВСА, ВСВСА, ВСВСВСА, ВСРСА, ВСОСВСА, ВСОСЬсА, ВСа6сА, ЬсайсА, Ьса6с). Соответствующий размеченный вывод (в данном случае единственный): ( А «, ВС »А я, ВСВС«А ь, ВСнВСВ е СА, ВСОС«А я, ВСОС» ВС»А, ВС ОС я ЬсА, е ВС аЬсА, ЬсаЬ *сА «, ЬсаЬс). Легко видеть, что 0(Г) = (а, Ьс)'. Грамматика Г= ( к, (р',1, )к) называется г р а м м а т ий *) оставляющих, или НС грамматика *), если каждое ее правило имеет вид йг $г- $«йг, где йь $г — произвольные цепочки в словаре У „ А ~ [(У и 9 — произвольная непустая цепочка в к'() («'. Правила вида йгА$г- йг0$г, где $ь йг, А и 9 имеют указанный только что смысл, иногда называют НС-пр авилами и; цепочка йь цепочка йг и пара цепочек ($ь йг) называются соответственно л е в ы м к о н т е к с т о м, правым контекстом и контекстом НС-правила й,Айг — $г9$г.
При применении НС-правила фактически заменяется только одно вхождение символа А, но возможность замены зависит от наличия нужного контекста. Если $, = йг —— Л, то правило называется бесконтекстным (нли контекстно-свободным), сок ащенно Б-правилом (или КС-правилом). Р НС-грамматика называется бесконтекстно" Й (нли контекстно-свободной), сокращенно Б грамматикой (или КСграмы атнкой), если исе ее правила бесконтскстные. (Б-) грамматика называется а в т о м а т н о й, сокращенно А-г р а м м а т и к о й *'), если каждое ее правило *) В «г амматикя состаиляющнх» часто говорят «грямматнка непосредственно (или непосредственных) составл щ »; место «р яю их»; от ение «НС-граммгтикк». Мы опускаем слово «непосредотяенно», тяк ккк никаких других составляющих не бывает (ср. [Гладкий — Мельяук 19691, отр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
