Файл: Алферова З.В. Теория алгоритмов учеб. пособие.pdf

В число аксиом, которые в геометрии Евклида принимаются без доказательств, входит и аксиома о параллельных линиях. Она формулировалась Евклидом так: «Если две прямые, лежащие в од­ ной плоскости, при пересечении их какой-нибудь третьей образуют внутренние односторонние углы, сумма которых меньше двух пря­ мых, то эти прямые пересекаются по ту сторону от третьей прямой, ,на которой сумма указанных углов меньше двух прямых».

Эта аксиома по многим причинам смущала математиков. Она значительно сложнее других аксиом и по утверждаемому ею факту и по своей формулировке. Ведь даже для осознания ее смысла на­ до предварительно овладеть рядом сведений.

Аксиому о параллельных линиях нередко называли темным пят­ ном в гениальном труде Евклида. Не была также доказана полно­ та и непротиворечивость евклидовой геометрии. И очень рано на­ чались упорные попытки математиков освободить евклидову геомет­ рию от всяких пятен.

С этой целью стремились доказать аксиому о параллельных. Пытались логически вывести ее утверждение из остальных аксиом Евклида. Такие попытки продолжались на протяжении двух с лиш­ ним тысячелетий. Почти все выдающиеся математики испытывали свои силы на решении этой проблемы (Декарт, Лейбниц, Гаусе и

ДР-)-

Полную бесплодность попыток доказать аксиому о параллель­ ных впервые строго научно установил великий русский математик Н. И. Лобачевский в X V I I I веке. Он доказал, что утверждение этой

.аксиомы нельзя вывести из остальных аксиом Евклида.

Лобачевский постулировал особую неевклидову геометрию, на­ званную его именем. Она отвергала истинность следующей аксио­ мы Евклида: «Если даны прямая и точка, не лежащая на ней, то существует только одна прямая, которая проходит через данную точку параллельно данной прямой». В геометрии Лобачевского па­ раллельных линий не существует. По отношению к этой новой гео­ метрии евклидова геометрия является только частным случаем.

Риман доказал, что неевклидова геометрия Лобачевского непро­ тиворечива, если непротиворечива евклидова геометрия, а Гильберт показал, что евклидова геометрия непротиворечива, если непроти­ воречива арифметика, т. е. элементарная теория положительных целых чисел.

Для доказательства непротиворечивости искали арифметиче­ скую логику, которая была бы полна, т. е. такую, в которой можно было бы вывести (как теоремы) все истинные утверждения о це­ лых числах.

Гёдель же показал тщетность таких поисков и доказал алгорит­ мическую неразрешимость проблемы доказательства непротиворе­ чивости арифметической логики. Таким образом, в своей теореме о неполноте Гёдель показал, что существует бесконечное число проб­ лем элементарной теории чисел, решение которых невозможно ни­ каким данным аксиоматическим методом.

.90

Г л а в а 2 ОСНОВЫ ТЕОРИИ ФОРМАЛЬНЫХ ГРАММАТИК

2.1. Основные понятия грамматик

четырьмя постановками различных задач, которые до этого раз­ вивались самостоятельно и, казалось, были мало связаны между собой. В последние годы общность этих задач и методов их иссле­ дования стала очевидной, их удалось объединить и понять как од­ ну общую задачу теории языков.

Перцре из этих направлений связано с построением формальной или математической лингвистики. Возникнув первоначально в свя­ зи с формальным изучением структуры литературного языка, мате­ матическая лингвистика начала особенно быстро развиваться, ког­ да были сформулированы, например, такие вопросы машинно­ го перевода: всякая ли фраза может быть переведена с одного язы­ ка на другой при заданном запасе правил в памяти машины; как описать множество текстов, доступных для перевода при заданных условиях. Попытка не только ответить, но даже точно поставить вопросы такого рода сразу же требовали формализации понятий «словарь», «грамматика», «язык», подразделения и классификации этих понятий и умения относить конкретные словари, грамматики, языки к тому или иному классу. Это послужило стимулом для большого числа работ, исследующих указанные понятия с позиций формальной лингвистики.

Появление искусственных машинных языков программирования еще более усилило интерес к задачам такого рода. Однако приня­ тый ранее в лингвистике изобретательский (эвристический) подход к новым языкам, при котором оценка удобства языка являлась де­ лом интуиции и опыта, оказался явно недостаточным для машин­ ных языков. Положение усугубилось появлением трансляторов, ко­ торые сделали проблему перевода центральной, во многом опреде­ ляющей построение общей теории вычислительных машин. Сами же машинные языки стали все более приближаться к формально построенным математическим конструкциям.

Совершенно независимо развивалось направление науки, свя­ занное с построением формальных моделей динамических систем. Эти модели должны были быть, с одной стороны, достаточно узки­ ми, чтобы допускать построение продуктивной теории, с другой — достаточно широкими, чтобы охватить некоторый общий класс при­ кладных задач.

Типичным примером такого рода является модель «конечный

92

автомат». Охватывая многие процессы, заданные на конечных мно­ жествах и развивающихся в счетном времени, конечные автоматы оказались вместе с тем настолько узкой моделью, что для них уда­ лось создать продуктивную теорию. Однако как только в эту мо­ дель вводилась бесконечность где-либо, кроме шкалы времени, это немедленно приводило к слишком общему классу систем (машины Тьюринга), эквивалентному столь широкому понятию, как произ­ вольный алгоритм.

Это породило многочисленные попытки построить промежуточ­ ные модели динамических систем, более широкие, чем конечный ав­ томат, но более узкие, чем машины Тьюринга, и как-либо класси­ фицировать эти модели. Была очевидна глубокая связь всех этих вопросов с теорией алгоритмов. Сама же постановка вопроса шла не от математической абстракции «алгоритм», а скорее от механи­ ческого формализма «динамическая система».

Независимо и параллельно развивалась общая теория алгорит­ мов как ветвь современной математики. Была установлена эквива­ лентность понятий «нормальный алгоритм Маркова», «общерекур­ сивная функция» и «машина Тьюринга», а тезис Черча связал эти три понятия с интуитивным представлением об алгоритме. Разви­ тие вычислительной техники поставило перед математической тео­ рией алгоритмов новую задачу: стало необходимо классифициро­ вать алгоритмы, например, по вычислительной сложности. Эквива­ лентность понятий «алгоритм» и «машина Тьюринга» сделала ес­ тественным предположение о том, что поиски классификации ал­ горитмов окажутся в известной мере связанными с поисками про­ межуточных моделей между моделями конечного автомата и ма­ шиной Тьюринга.

Таким образом, перечисленные четыре направления оказались тесно связанными. Естественно поэтому, что теория языков, по­ рожденная чисто лингвистическими задачами, оказалась в центре интересов математиков, занимающихся теорией алгоритмов, и уче­ ных, занимающихся абстрактными моделями динамических систем, а в последние годы — в центре интересов ученых, разрабатываю­ щих теоретические основы автоматики. .

Теория формальных грамматик и языков является основным разделом математической лингвистики — специфической математи­ ческой дисциплины, ориентированной на изучение структуры есте­ ственных и искусственных языков.

Эта теория возникла в 50-е годы в работах американского линг­ виста Н. Хомского (хотя основы аппарата, на котором она базирует­ ся, были разработаны в математической лингвистике значительно раньше). При этом Хомский исходил исключительно из потребно­ стей лингвистики, по традиции, понимаемой как наука о строении естественных языков. Однако очень скоро обнаружилось, что мето­ ды его теории в не меньшей степени приложимы к искусственным

и лучше поддаются формализации, чем естественные языки.

93

По характеру используемого математического аппарата теория формальных грамматик и языков близка к теории алгоритмов и к

вил, определяющих этот язык. Грамматику языка можно рассмат­ ривать как теорию структуры этого языка, т. е. теорию повторяю­ щихся закономерностей построения предложений, называемых син­ таксической структурой языка.

толкование этих правил, правила использования синтаксиса. Итак, грамматика языка это конечное множество правил, рекурсивно за­ дающих язык как синтаксическую структуру.

Грамматика играет роль повторяющихся закономерностей по­ строения предложений языка, которые отражают синтаксическую структуру его. Отсюда первое и основное требование к формали­ зуемой грамматике — чтобы она приписывала каждому предложе­ нию языка его структурное описание. Это правило определяет, из каких элементов построено предложение, каков их порядок, распо­ ложение.

Структурное описание будет тогда и только тогда однозначно, когда в языке через грамматику однозначно определены его син­ таксические единицы и иерархическая взаимосвязь между ними.

;Второе требование к грамматике языка — грамматика должна

/быть конечной, т. е. если допустить грамматики с неопределенным множеством правил, то сама проблема построения грамматик сни­ мается.

Формальные грамматики имеют дело с абстракциями, возни­ кающими путем обобщения понятий словоформа, словосочетание, предложение.

Если обычные грамматики позволяют задавать множества прат вил построения предложений, то формальные грамматики — это не­ который способ изучать и описывать множества правил.

Между обычными и формальными грамматиками имеется суг щественное различие. В формальных грамматиках все утверждения формулируются в терминах небольшого числа четко определенных

94

и весьма элементарных символов и операций. Это делает формаль­ ные грамматики сравнительно простыми с точки зрения их логиче­ ского строения и облегчает изучение их свойств.

Однако формальные грамматики оказываются весьма громозд­ кими для описания естественного 'языка и поэтому предназначают­ ся сугубо для научного, теоретического исследования наиболее об­ щих свойств языка.

любой рассматриваемой цепочки она умеет решить, является эта цепочка правильной или нет, и в случае положительного ответа дать указания о строении этой цепочки.

Формальная грамматика называется порождающей, если умеет построить любую правильную цепочку, давая при этом указания о ее строении, и не строит ни одной неправильной цепочки.

Формальная грамматика называется преобразующей, если для любой правильно построенной цепочки она умеет построить ее ото­ бражения опять же в виде правильной цепочки, задавая при этом

чаются классы или цепочки исходных элементов, или словарь син­ таксических типов.

Элементы VT и VH называются соответственно терминальными или нетерминальными символами. V = V T U VH — конечное множе­ ство символов, называемое словарем грамматики G. Произвольную конечную последовательность со элементов V будем называть це­ почкой в словаре V. Пустая цепочка обозначается Л > таким обра­ зом со д = д со = со. Число членов этой конечной последовательно­ сти назовем длиной цепочки и будем обозначать |со|.

Цепочки символов словаря V получаются с помощью операции

соединения (конкатенации) гл . Например, со = aia2 a3 . Если не воз­ никает неоднозначности, символ гл может опускаться. Операция соединения ассоциативна, но не коммутативна.

символ 5 называется еще аксиомой, или целью грамматики.

95