ВУЗ:
Составители:
Обратимся теперь к проблеме эквивалентности слов в комбинаторной
системе, сущность которой была рассмотрена в разделе 1.1. Ясно, что
установить, эквивалентно ли слово А слову В, или выяснить, является ли В
формулой данной туэвской системы, равносильно. Возьмем построенную
выше туэвскую систему с неразрешимой проблемой доказуемости и
поставим ей в соответствие ассоциативное исчисление,
полученное путем
замены каждой пары туэвских подстановок соответствующим соотношением
Туэ. Легко видеть, что для этого ассоциативного исчисления проблема
эквивалентности слов неразрешима.
3. ФОРМАЛЬНЫЕ ГРАММАТИКИ И ЯЗЫКИ
3.1. Порождающие грамматики
Любой формальный язык можно рассматривать как набор правильных
предложений, построенных по правилам синтаксиса языка и имеющих
определенный смысл. Для описания синтаксиса
средств самого языка не
хватает. Поэтому для этой цели используют метаязыки, в которые помимо
символов самого языка входят так называемые метасинтаксические (или
металингвистические) переменные. Язык можно задать двумя методами:
описанием процедуры построения правильных конструкций (этот процесс
называется порождением) или распознаванием правильности конструкции.
Наиболее часто используют первый метод. Второй метод, как правило
,
реализуется аппаратом распознающих автоматов, которые являются
разновидность машин Тьюринга с различными ограничениями.
Для описания синтаксиса алгоритмических языков можно использовать
язык нормальных форм Бэкуса (НФБ). Этот язык был введен для описания
синтаксиса языка Алгол-60. Его развитие использовано для описания языков
Фортран, ПЛ/1, Алгол-68. НФБ позволяет формально строить предложения
Алгола-60. Помимо символом
моделируемого языка НФБ включает
следующие металингвистические переменные: ::= - связка, которая означает
Страницы
- « первая
- ‹ предыдущая
- …
- 45
- 46
- 47
- 48
- 49
- …
- следующая ›
- последняя »
