Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
') Описанная здесь процедура годится, разумеется, лишь для простейшего случая, когда искомое слово имеет словарную форму (например, для русского языка, существительные — в им. пад. ед. числа, глаголы — в инфинитиве и т. д). Более общая ситуация (для языков, где имеется словоизменение) предполагает предварительное приведение текстового слова к словарному виду. — Прим. перев. 66
Часть /. Предварительные сведения из логики и алгебры
4.1.2. Алгоритмы и формальные грамматики
Понятие алгоритма используется в формальной лингвистике, в частности, следующим образом.
Выше (стр. 23) мы определили (формальный) язык L над алфавитом ЇЇ (над словарем 33): L есть множество слов (фраз), принадлежащих свободной полугруппе її* (соответственно 33*) с системой образующих її (соответственно 33). Язык L представляет собой множество допустимых, т. е. (синтаксически) правильных слов (фраз). Поэтому %*\L есть множество недопустимых, т. е. неправильных слов (фраз).
Формальная грамматика должна дать правила, которые обеспечивают либо получение правильно построенных слов (правильных фраз), либо распознавание того, является ли данная цепочка букв (слов) правильно построенным словом (правильной фразой). Другими словами, цель грамматики состоит в том, чтобы как-то задать (охарактеризовать) слова (фразы), принадлежащие данному языку. Таким образом, формальная грамматика предстает как алгоритм, а именно, как совокупность правил, позволяющих задать некоторый язык1).
Если предположить, что у нас имеется алгоритм (в смысле, указанном в предыдущем пункте), такой, что его входными символами являются имена целых чисел 1, 2, ..., п и каждому входному символу отвечает на выходе некоторое слово (фраза) языка, определяемого данным алгоритмом, то мы можем сказать, что этот алгоритм— или грамматика — перечисляет слова (фразы) этого языка.
Пример 1. Алфавит її = {0, 1, 2, 3,4, 5, 6, 7, 8, 9}; слово принадлежит языку L тогда и только тогда, когда оно является десятичным представлением простого числа.
Алгоритм, задающий язык L, легко себе представить; он может быть основан, например, на решете Эратосфена.
Пример 2. Алфавит її = {1, 2,3,4,5,6, 7,8, 9}; язык L определяется следующим образом.
Рассмотрим (бесконечное) десятичное разложение числа п. Цепочка цифр является словом языка L тогда и только тогда, когда она встречается в этом разложении между двумя последователь-
') Утверждение, что грамматика — это алгоритм, содержит неточность. В математической логике различаются понятия алгоритма и исчисления, в наиболее общем виде можно, следуя А. А. Маркову, охарактеризовать алгоритм как предписание, а исчисление — как разрешение производить некоторые действия. В частности, (детерминированная) машина Тьюринга — это один из способов реализации алгоритма, а комбинаторные системы — это исчисления. Грамматики, как они здесь (и обычно) определяются, представляют собой исчисления, поскольку в них нет ограничений на порядок применения правил. Чтобы превратить грамматику в алгоритм, необходимо присоединить к ней какой-либо механизм, устанавливающий жесткий порядок применения правил. Ср. Гладкий — Мельчук [1969], стр. 45—46. — Прим. ред. Гл. IV. Алгоритмы. Машины Тьюринга
67
ными вхождениями символа 0. Алгоритм, задающий этот язык, основывается на вычислении числа л.
Естественным образом возникает следующая алгоритмическая проблема:
По данной цепочке вхождений букв (слов) узнать, является ли она правильно построенным словом (правильной фразой) данного языка.
Пример. Всякий язык программирования состоит из исходных символов и правил образования выражений; правила приводятся в инструкции по использованию языка. (Если это хорошая инструкция, она представляет собой грамматику данного языка.) Правильная программа является правильной фразой языка, и обратно.
Компилирование программы, написанной на некотором языке программирования, для определенной конкретной машины — это операция, которую достаточно трудно определить формально. Грубо говоря, мы можем рассматривать компилирование программ как «перевод» с одного языка на другой: правильным цепочкам входного языка должны соответствовать правильные цепочки выходного языка. Процесс компилирования включает проверку синтаксической правильности входной программы. Эта проверка осуществляется специальным алгоритмом, имеющим два особых выходных символэ, содержательный смысл которых — «правильно» и «неправильно».
Легко убедиться, что наличие алгоритма перечисления цепочек еще не гарантирует существования алгоритма распознавания их правильности. В примере 1 этого пункта алгоритм, позволяющий узнать, является ли данное число простым, существует. Однако в примере 2 дело обстоит иначе: по крайней мере, насколько известно авторам, пока что никем не предложен алгоритм, позволяющий узнать, является ли данная цепочка словом из L. Быть может, когда-нибудь удастся доказать, что такой алгоритм вообще нельзя построить.
До сих пор мы имели дело с чисто интуитивным понятием алгоритма. Его, однако, можно формализовать, что и было в свое время сделано с помощью ряда конструкций, которые в конце концов оказались эквивалентными. В частности, для формализации понятия «алгоритм» привлекались комбинаторные системы, о которых шла речь выше, и так называемые машины Тьюринга, которые будут рассматриваться в этой главе.
