Теория формальных грамматик - раздел дискретной математики, изучающий способы описания закономерностей, характеризующих всю совокупность правильных текстов того или иного языка. Формальные грамматики - это абстрактные системы, позволяющие с помощью единообразных процедур получать правильные тексты данного языка вместе с описанием их структуры. Теория формальных грамматик занимает центральное место в математической лингвистике, так как именно она позволяет моделировать наиболее существенный аспект функционирования языка - переработку смыслов в тексты и обратно. Вместе с тем она выделяется среди других разделов математической лингвистики большей сложностью математического аппарата (сходного с аппаратом теории алгоритмов и общей теории автоматов) и возникающих в ней математических задач. Формальные грамматики наиболее разработанных типов представляют собой системы (╚устройства╩), которые позволяют порождать или распознавать множества конечных последовательностей (цепочек), интерпретируемые обычно как множества правильных предложений, а также сопоставлять входящим в эти множества цепочкам описания их синтаксической структуры в терминах систем составляющих или деревьев подчинения.
Порождающая грамматика состоит из четырех компонент: Г = (V, W, J, R), где V и W - непересекающиеся конечные множества, называющиеся основным и вспомогательнымалфавитами (или словарями); элементы этих множеств называются соответственно основными (или терминальными) и вспомогательными (или нетерминальными) символами; J - выделенный вспомогательный символ, называемый начальным символом; R - конечный набор правил вывода, имеющих вид j (r) y, где j и y - цепочки, состоящие из основных и вспомогательных символов.
Основные символы интерпретируются как слова языка, вспомогательные - как имена классов слов и словосочетаний, начальный символ - как символ предложения (т.е. имя класса словосочетаний, являющихся предложениями). Правила вывода описывают связи между частями предложения. Применение правила j (r) y к цепочке, имеющей вид a j b, означает преобразование ее в цепочку ay b (здесь a и b - цепочки, одна из которых или обе могут быть пустыми). Вывод в порождающей грамматике есть конечная последовательность цепочек, в которой каждая следующая цепочка получается из предыдущей использованием каких-либо правил вывода. Последняя цепочка вывода называется выводимой из первой. Цепочка основных символов, выводимая из начального символа, называется предложением, а множество всех предложений - языком, порожденным данной грамматикой.
Пример. В грамматике с основным алфавитом {a, b, c}, вспомогательным алфавитом {a, b}, начальным символом a и набором правил {a(r) aab, a(r) bc, b (r) b} одним из выводов будет последовательность a, aab, abcb, abcb, abcb; цепочка abcb - предложение.
В зависимости от вида правил выделяется ряд основных классов порождающих грамматик. Наиболее важны для лингвистических приложений грамматики составляющих (грамматики непосредственно составляющих - НС-грамматики, контекстные грамматики), правила вывода которых имеют вид c aw (r) c yw , где a - вспомогательный символ, y - непустая цепочка, c и w - произвольные цепочки. Важнейший подкласс грамматик составляющих - бесконтекстные грамматики (контекстно-свободные грамматики - КС-грамматики), у которых правила имеют вид a (r) y . Частный случай бесконтекстной грамматики - автоматная грамматика(грамматика с конечным числом состояний) с правилами вывода a(r) ab и a(r) a, где a - основной символ, a и b - вспомогательные символы. Языки, порождаемые грамматиками перечисленных классов, называются соответственно НС-языками (контекстными языками) и КС-языками (бесконтекстными, автоматными).
В грамматиках составляющих на каждом шаге вывода заменяется только один символ, поэтому в них с каждым выводом ассоциируется так называемое дерево вывода. Корень дерева отвечает начальному символу. Каждому символу цепочки, на которую заменяется начальный символ на первом шаге вывода, ставится в соответствие узел дерева, и к нему проводится дуга из корня. Для тех из полученных узлов, которые помечены вспомогательными символами, делается аналогичное построение и т.д. Дерево вывода, рассматриваемое как дерево составляющих предложения, задает на нем систему составляющих. Это делает грамматики составляющих хорошим инструментом для описания естественных и искусственных языков.
Еще один важный класс формальных грамматик - доминационые грамматики, позволяющие порождать цепочки, одновременно строя для них деревья подчинения.
Для описания естественных языков наиболее
адекватны трансформационные грамматики, в которых преобразуются
не цепочки, а непосредственно синтаксические структуры - деревья составляющих
или деревья подчинения.
Теория алгоритмов
Теория алгоритмов - раздел математики, изучающий общие свойства алгоритмов.
Алгоритм, алгорифм, - точное предписание, которое задает вычислительный процесс (называемый в этом случае алгоритмическим), начинающийся с некоторого исходного данного (из некоторой совокупности возможных для данного алгоритма исходных данных) и направленный на получение полностью определяемого этим исходным алгоритмом результата.
╚Уточнение╩ понятия алгоритма. Как правило, для данного алгоритма можно выделить семь характеризующих его параметров:
1) совокупность возможных исходных данных,
2) совокупность возможных результатов,
3) совокупность возможных промежуточных результатов,
4) правило начала,
5) правило непосредственной переработки,
6) правило окончания,
7) правило извлечения результата.
Понятие алгоритма в общем его виде принадлежит к числу основных первоначальных понятий математики, не допускающих определения в терминах более простых понятий. Возможные уточнения понятия алгоритма приводят, строго говоря, к известному сужению этого понятия. Каждое такое уточнение состоит в том, что для каждого из указанных семи параметров алгоритма точно описывается некоторый класс, в пределах которого этот параметр может меняться. Выбор таких классов и отличает одно уточнение от другого. Поскольку семь параметров однозначно определяют некоторый алгоритм, то выбор семи классов изменения этих параметров определяет некоторый класс алгоритмов. Однако такой выбор может претендовать на название ╚уточнения╩, лишь если имеется убеждение, что для произвольного алгоритма, имеющего допускаемые данным выбором совокупность возможных исходных данных и совокупность возможных результатов, может быть указан равносильный ему алгоритм из определенного данным выбором класса алгоритмов.
Это убеждение формулируется для каждого уточнения в виде основной гипотезы, которая (при современном уровне наших представлений) не может быть предметом математического доказательства.
Алгоритмы прослеживаются в математике в течение всего времени ее существования. Общее понятие алгоритма сформировалось, однако, лишь в 20 веке и впервые появилось в трудах Э. Бореля (1912) и Г. Вейля (1921). Началом систематической разработки теории алгоритмов можно считать 1936 год, когда А.Черч опубликовал первое понятие вычислимой функции и привел первый пример функции, не являющейся вычислимой, а А. Тьюринг и Э. Пост дали первые уточнения понятия алгоритма (в терминах идеализированных вычислительных машин, машин Тьюринга), их конструкции во многом предвосхитили идеи, заложенные в основу современных цифровых вычислительных машин. В дальнейшем теория алгоритмов получила развитие в трудах С. Клини, Э. Поста, А.А. Маркова, А.Н. Колмогорова и других. В частности, А.А. Марков предложил уточнять понятие алгоритма с помощью введенного им понятия нормального алгорифма. Наиболее общий подход к уточнению понятия алгоритма предложил А.Н. Колмогоров: трактовать конструктивные объекты как топологические комплексы определенного вида, что дало возможность уточнить свойство ╚локальности╩ преобразования.
Основные понятия теории алгоритмов. Областью применимости алгоритма называется совокупность тех объектов, к которым он применим, т.е. в применении к которым дает результат.
Про алгоритм А говорят, что он
1) ╚вычисляет функцию f╩, коль скоро его область применимости совпадает с областью определения f, и А перерабатывает всякий x из своей области применимости в f(x);
2) ╚разрешает множество A относительно множества X╩, коль скоро он применим ко всякому x из X, и перерабатывает всякий x из X ЗA в слово ╚да╩, а всякий x из X \ A - в слово ╚нет╩;
3) ╚перечисляет множество B╩, коль скоро его область применимости есть натуральный ряд, а совокупность результатов есть B.
Функция называется вычислимой, если существует вычисляющий ее алгоритм. Множество называется разрешимым относительно X, если существует разрешающий его относительно X алгоритм. Множество называется перечислимым, если либо оно пусто, либо существует перечисляющий его алгоритм.
Детальный анализ понятия ╚алгоритм╩ обнаруживает, что
(I) область возможных исходных данных и область применимости любого алгоритма суть перечислимые множества. В свою очередь,
(II) для любой пары вложенных одно в другое перечислимых множеств можно подобрать алгоритм, у которого большее множество служит областью возможных исходных данных, а меньшее - областью применимости.
Имеют место следующие основные теоремы:
(III) функция f вычислима тогда и только тогда, когда перечислим ее график, т.е. множество всех пар вида бx, f(x)с .
(IV) Подмножество A перечислимого множества X тогда и только тогда разрешимо относительно X, когда A и X \ A перечислимы.
(V) Если A и B перечислимы, то AИ B и AЗ B также перечислимы.
(VI) В каждом бесконечном перечислимом множестве X существует перечислимое подмножество с неперечислимым дополнением (в силу (IV) это перечислимое подмножество будет неразрешимым относительно X).
(VII) Для каждого бесконечного перечислимого множества X существует вычислимая функция, определенная на подмножестве этого множества и не продолжаемая до вычислимой функции, определенной на всем X.
Утверждения (VI) и (II) в совокупности дают пример алгоритма с неразрешимой областью применимости.
Разрешимые и перечислимые множества составляют простейшие (и наиболее важные) примеры множеств, строение которых задается с помощью тех или иных алгоритмических процедур. Систематическое изучение множеств конструктивных объектов с точки зрения таких свойств этих множеств, которые связаны с наличием тех или иных алгоритмов, образует т.н. алгоритмическую теорию множеств.
Теорию алгоритмов можно разделить на дескриптивную (качественную) и метрическую (количественную). Первая исследует алгоритмы с точки зрения устанавливаемого ими соответствия между исходными данными и результатами; к ней относятся, в частности, проблемы построения алгоритма, обладающего теми или иными свойствами, - алгоритмические проблемы. Вторая исследует алгоритмы с точки зрения сложности как самих алгоритмов, так и задаваемых ими вычислений, т.е. процессов последовательного преобразования конструктивных объектов. Важно подчеркнуть, что как сложность алгоритмов, так и сложность вычислений могут определяться различными способами. Разработка методов оценки сложности алгоритмов и вычислений имеет важное теоретическое и практическое значение.
Приложения теории алгоритмов имеются во всех областях математики, в которых встречаются алгоритмические проблемы. Такие проблемы возникают практически во всех разделах математики. В математической логике для каждой теории формулируется проблема разрешения множества всех истинных или доказуемых предложений этой теории относительно множества всех ее предложений (теории подразделяются на разрешимые и неразрешимые - в зависимости от разрешимости или неразрешимости указанной проблемы); в 1936 году Черч установил неразрешимость проблемы разрешения для множества всех истинных предложений логики предикатов, дальнейшие важные результаты в этом направлении принадлежат А. Тарскому, А.И Мальцеву и др.
Неразрешимые алгоритмические проблемы встречаются:
1) с математической логикой, поскольку в терминах теории алгоритмов может быть изложено одно из центральных понятий математической логики - понятие исчисления (и потому, например, теорема Геделя о неполноте формальных систем может быть получена как следствие теорем теории алгоритмов);
2) с основаниями математики, в которых одно из центральных мест занимает проблема соотношения конструктивного и неконструктивного (в частности, теория алгоритмов дает аппарат, необходимый для разработки конструктивного направления в математике); в 1965 году А.Н. Колмогоров предложил использовать теорию алгоритмов для обоснования теории информации;
3) с кибернетикой, в которой важное место занимает изучение алгоритмов управления;
4) теория алгоритмов образует теоретический
фундамент для рядя вопросов вычислительной математики.