Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 54
Текст из файла (страница 54)
Так как е! — слово в А, то либо зг у (ио тогда этот отрезок из вывода можно удалить), либо на о~резке т';е была применена по ь крайней мере одна из продукций (6.!6). Для любого вывода, содержащего между словами из А несколько нрименений продукций (6.16), в йгб можно построить эквивалентный вывод, в котором между этими применениями вставлены слова из А. Строгое доказательство этого утверждения опускаем; приведем лишь пример: выводу сг,газ!-гззр 1- !-р!))з1- ()з6г1- р1рз, в котором применены продукции к,х~хр, и итх~ = хрз, соответствует вывод сс,а,1-сгзр, 1-(),аз ь р,ат ь-азр,"-р,рт ! Нз, в котором они разделены словом Ргиь Итак, можно считать, что в выводе ть-ег продукция (6,16) — пусть это будет сгх-.хР' — применена ровно один раз. Но тогда у=титу„применению продукции (6.16) предшествовало несколько (быть может, нн одного) применений (бнт) н место вывода, где применена продукция (6.16), имеет вид гху,т,~ ~рту,Р'.
Остаток угу!Р,ь.е, рассматриваемого отрезка не содержит применений (6.16), поэтому в силу свойств продукций (6.17), (6.18) ей=у~Рте. Но тогда ег получается из у подстановкой гз-~р, т,е тыег в Я. Индукцией по числу слов ег.доказываем, что уьб в Б. Отсюда следует эквивалентность я и !уя, после чего о справедливости теоремы нетрудно заключить из сопоставлевия теорем 6.15 н 6.18.
В заключение главы приведем без доказательства один результат об алгоритмической неразрешимости, который доказан Постом с помощью канонических систем и который часто используется для доказательства других неразрешимостей (особенно в теории формальных грамматик). Пусть дано конечное множество (аь р!), ..., (а, й ) пар слов в алфавите А. Поставим следующую проблему; существует ли последовательность (!, (з, ..., (н индексов, такая, что оба;,... а,!,=~)й~г, ...
р! р Эта проблема называется комбинаторной проблемой, или проблемой соответствия Поста. Имеются два варианта ее формулировки: общая комбинаторная проблема Поста (для произвольного множества пар) н ограниченная комбинаторная проблема (для множества пар с фиксированной мощностью пт). Теорема 6.20. Ограниченная комбннаторная проблема 17* 269 Поста для достаточно больших т алгоритмнчески неразрешима. Отсюда следует неразрешимость и общей комбинаторной проблемы.
формальные системы и алгоритмы. Итак, формальныа системы оказываются столь же мощным средством для задания конструктивных объектов, что и алгоритмы. С их помощью можно имитировать поведение машин Тьюринга, т. е. строить формальные системы, в некотором смысле аналогичные алгоритмам. С другой стороны, понятие перечислимого множества в терминах формальных систем (опирающееся на теорему 6.18) выглядит более компактным, чем в терминах, скажем, машины Тьюринга.
Поэтому возможны две концепции построения системы основных понятий, формализующих идеи эффективности и конструктивности. Концепция, описанная ранее и являющаяся исторически первой, кладет в основу понятие алгоритма. Вторая концепция, созданная Э. Постом', опирается на понятия формальной (конкретнее, канонической) системы и перечислимого множества, которое определяется просто как множество теорем формальной системы. Нормальную канойическую систему над алфавитом А можно представить как граф с одной выделенной вершиной — аксиомой, остальные вершины которого помечены словами вА — теоремами, ребра — это применения продукций, а пути из вы)1елейной вершины в данную — возможные выводы данного слова.
Множество слов в А, порождаемое системой,— это множество всех вершин графа, помеченных словама вА. Алгоритм — это формальная система особого, детерминированного вида, характеризующаяся тем, что в ней к каждой теореме применима не более чем одна продукция. Соответствующий граф представляет собой цепочку, изображающую вычислительный процесс; аксиома в таком графе — это просто исходные данные алгоритма. Другой способ детерминизации формальных систем— это фиксация порядка применения правил вывода. Например, нормальный алгоритм Маркова 1411 †э упорядоченная система подстановок с двумя дополнительными сО- глашениями: 1) гъя подстановка может быть применена, только если неприменимы 1, ..., (1 — 1)-я подстановки; 2) если подстановка а- р применима к слову у, то р подставляет- ' Сжатое и блестяиге наиисаиное изложение этой ноннеинии име.
ется а книге Мартин-Лефа (421. 260 ся вместо самого левого вхождения а в у. Основной акцент «алгоритмической» концепции — в ее детерминизме. По. этому она естественна и удобна при описании вычислительных процессов и устройств. Основной акцент «формально- системной» концепции — в компактности конструктивного описания множеств. Примеры такого описания — формальные теории (5 6.1 н 6.2). Другая группа примеров, крайне важных в прикладном отношении,— это алгоритмические языки программирования. Методы описания языков и построения компиляторов для них опираются на теорию формальньи грамматик, представляющих собой еще один вид абстрактных формальных систем, Основные понятия этой теории изложены в следующей главе.
ГЛАВА СЕДЬМАЯ ЯЗЫКИ И ГРАММАТИКИ До начала ХХ в., говоря о языках, имели в виду только естественные языки (русский, английский, латинский и т, д.), являющиеся или являвшиеся в прошлом средством общения между людьми в их обычной повседневной жизни. Наука о языках — лингвистика — сводилась в основном к изучению конкретных естественных языков, нх классификации, выяснению сходств и различий между ними.
Возникновение и развитие метаматематнки (см. гл. 5 и 6), изучающей по существу язык математики, логико-фи. лософские исследования языка науки, предпринятые Л. Виттгенштейном, Р. Карнапом и другими в 20 — 30-е гг., исследования средств коммуникации у животных, идеи структуралистского подхода к лингвистике привели в 30-х гг. к существенно более широкому представлению о языке, при котором под языком понимается всякое средство общения, состоящее из: 1) знаковой системы, т.е, множества допустимых последовательностей знаков; 2) множества смыслов этой системы; 3) соответствия между последова тельностями знаков и смыслами, дела!ощего «осмысленными» допустимые последовательности знаков, Знаками могут быть буквы алфавита, математические обозначения, звуки, движения брачного танца у животных, ритуальные действия в обрядах различных народов.
Наука об осмысленных знаковых системах называется семиотикой. Семиотический подход оказывается весьма плодотворным в раз- 26! личных областях знания — в биологии, социологии, этнографии, лингвистике; при этом разные ветви семиотики имеют значительную специфику н не везде еще используют точные математические средства. Наиболее продвинутыми являются исследования знаковых систем, в которых знаками являются символы алфавитов, а последовательностями знаков в тексты; к таким знаковым системам относятся естественные языки, языки науки, а также сильно развившиеся в последние 30 лет язьгки программирования. Именно интерес к языкам программирования, совпавший с новыми подходами в структурной лингвистике и необходимостью решать задачу машинного перевода естественных языков, привел в 50-х гг.
к возникновению новой науки — математической лингвистики, которая рассматривает языки как произвольные множества осмысленных текстов. Правила, определяющие множество текстов, образуют синтаксис языка; описание множества смыслов и соответствия между текстами и смыслами — семантику языка. Семантика языка зависит от характера объектов, которые описываются языком, и средства ее изучения для различных типов языков различны. О семантике языка математики — формальных теорий — речь шла выше, в 3 6.3; исследование семантики языков программирования стало самостоятельной отраслью теоретического программирования; попытки точного описания семантики естественных языков связаны прежде всего с работами по машинному переводу. Что же касается синтаксиса, то его особенности гораздо меньше зависят от назначения и целей языка; оказывается возможным сформулировать понятия и методы исследования синтаксиса языков, не зависящие от содержания н назначения языков.
Кроме того, как уже отмечалось при обсуждении теоремы Райса (см. гл. 5), синтаксические свойства языков проще изучать и распознавать, чем семантические (хотя и при изучении синтаксиса, как будет видно далее, возникают алгоритмически неразрешимые проблемы). Поэтому наибольших успехов математическая лингвистика достигла в изучении синтаксиса, где за последние 30 лет сложился специальный математический аппарат — теория формальных грамматик, очень содержательный и интересный разговор в теоретическом отношении и эффективный в приложениях (языки программирования, искусственный интеллект, машинный перевод), Именноэтот аппарат и будет предметом настоящей главы.
С точки зрения синтаксиса язык понимается уже не как 262 средство общения, а как множество формальных (в смысле теории формальных систем — см. начало гл. 6 и $6.4) объектов — последовательностей символов алфавита. Такие последовательности выше назывались текстами; в теории алгоритмов н формальных систем их называют словами (см. пример 1.5, а также $ 5.1, 5.2 и 6.4), В лингвистике естественных языков термины «текст» и «слово» имеют разный смысл; поэтому в математической лингвистике последовательность символов обычно называют нейтральным термином «цепочка» (з!г!пя), а язык, понимаемый как множество формальных цепочек, — формальным языком.
До конца этой главы, говоря о языках, будем иметь в виду формальные языки, если не оговорено противное. тя. ФОРМАЛЬНЫЕ ГРАММАТИКИ И ИХ СВОЙСТВА Пусть задан алфавит У и тем самым множество У" всех конечных слов, или цепочек, в алфавите У. Формальный язык 1. в алфавите У вЂ” это произвольное подмножество 1,«:-У*. Конструктивное описание формальных языков осуществляется с помощью формальных систем специального вида, называемых формальными порождающими грамматиками.
Формальная порождающая грамматика 6 (в дальнейшем — просто грамматика 6) — это формальная система, определяемая четверкой объектов 6= ( У, Ф', 1, Р ), где У вЂ” алфавит (или словарь) терминальных (основных) символов; Я7 — алфавит нетерминальных (вспомогательных) символов; УПВ'= Я; 1 — начальный символ (аксиома) грамматики; Р— конечное множество правил вида $-»т1, где $ и т! — цепочки в алфавите У()!Р, Цепочка 5 непосредственно выводима из цепочки а в грамматике 6 (обозначение а=»вр; индекс 6 опускается, если понятно, о какой грамматике идет речь), если а=Т$5, Д=ут15 и 5- -»т! — правило 6. Цепочка р выводима из а, если существует последовательность ео=а, ео еь ..., е,=р, такая, что для всех 1=О,..., п — 1 е;=:-еы.ь Эта последовательность называется выводом Д из а, а и (число ее элементов, отличных от а) — длиной вывода.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
