Файл: Богданов В.С. Системы математического обеспечения цифровых вычислительных машин учеб. пособие.pdf

- 19 -

том, что в реальной ЦВМ возможны статистические нарушения де­ терминированности (влияния помех).

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

§ 5. Алгоритмическая неразрешимость

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

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

Впервые примеры алгоритмической неразрешимости были по­ строены Марковым и Постои в 1947 году; однако они были гро­ моздкими и включали сотни подстановок. Позднее ленинградский

- 20 -

математик Г.С. Цейтлин привел пример, насчитывающий лишь семь допустимых подстановок. Наряду с такими центральными проблемами теории алгоритмов, как уточнение понятий алгорит­

ма', алгоритмической неразрешимости, в связи с проектированием ЦВМ возникли прикладные, такие, как конструирование алгорит­

§ б. Элементы теории формальных языков

Разработка и применение алгоритмических языков базиру­ ется на математическом аппарате, разрабатываемом недавно возникшей и успешно развивающейся наукой - математической лингвистикой. Ниже рассматриваются основные понятия и неко­ торые результаты математической лингвистики, имеющие отно­ шение к разработке алгоритмических языков.'

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

- 21 -

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

мыслимо без передачи информации о различных событиях. Еассмат-

.ривая более внимательно процесс передачи информации (речевой),

мокно придти к выводу, что он проходит в двух планах: выра­ жения и содержания. Содержание (смысл) представляет­

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

План содержания можно рассматривать как некоторое мно­

жество "рныслов", а план выражения - как некоторое множество “текстов". Между смыслами и текстами имеется вполне определен­ ное соответствие: каждому смыслу отвечает более или менее оп­ ределенная совокупность текстов. Правила, определявшие, ка­ кие тексты соответствуют таким смыслам, и образуют по сущест­

текстов.

Эта функция является эффективно вычисленной, поскольку язык представляет собой способ эффективного получения текс­ тов по заданным смыслам (функцию F (x) принято называть эф- - фективно вычисленной, если для нее указан вполне определен­ ный способ, позволяющий для любого значения X найти за ко­

нечное число шагов значение F (x ), то есть если она может быть вычислена на машине).

Язык - это система, состоящая из объектов различных уровч

- 22

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

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

В математической символике изучается формальные грамиатики,-

Из яабора некоторых символов можно строить самые различ-

<а

ные цепочки-; некоторые цепочки в данном языке считается пра­ вильными', а некоторые неправильными. Формальная грамматика задает правильные цепочки, если имеет место одно из двух ус­ ловий:

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

2)грамматика умеет построить любуе правильную цепоч­ ку и не строит неправильных.

Грамматика первого типа называется распознающей, второ­ го типа - порождающей.

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

■“ ■Теория формальных грамматик служит' основой теории -так

называемых контекстно-свободных-языков, к классу которых при-

9

надлежат различные алгоритмические языкя.

- 23 -

Наиболее широко в настоящее время в теории языков про­

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

ющие части.

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

2. Вспомогательный (нетерминальный) словарь - набор сим­ волов, которыми обозначаются классы элементов или цепочек -

инекоторые специальные элементы.

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

4. Правила подстановки - выражение вида "Х-’ -У1' , что означает замену X на У, где X и У цепочки, содержащие любые терминальные и нетерминальные символы.

Правила подстановки позволяют Формировать алгоритмичес­

ки (на вычислительной машине) правильные грамматически выра­ жения на-данном языке (сравните с нормальными алгоритмами

Маркова).. ■ Следует подчеркнуть, что порождающая грамматика не яв­

ляется алгоритмом; правила подстановки - это не последова-

е . тельность, а совокупность разрешений. Это означает, что пра­

торых можно дать определение языка, порождаемого грамматикой.

ке, называется языком, порождаемым данной грамматикой.

Язык, таким образом, - это множество цепочек, выводов,

порождаемых данной грамматикой.

Существует несколько типов грамматик, среди которых для

теории языков программирования наибольший интерес представ­ ляют так называемые контекстно-свободные грамматики (КС-граы- натики), порождающие контекстно-свободные языки.

Терминальная цепочка X может иметь вид Z,CZS . Тогда правило ZtCZ2 ~*~Z, WZz означает разрешение заменить С на

Wтолько в данном контексте Z ,......Ег .

Сам кон-текст при замене переписывается без изменения. Правила замена, используемые контекстом, называются контекст­ но-связанными, а правила, в которых замена производится без использования контекста, называются контекстно-свободными.

Грамматики, -содержащие только контекстно-свободпые пра­ вила'5, называются контекстно-свободными, или КС-граыаатикаіш. В левой части правила подстановки X -*-У стоит один символ'