Составители:
9
На первый вопрос ответить легко, если язык конечен. Надо просто
перечислить все предложения, т.е. составить список. Если язык бесконечен, то
возникает проблема нахождения способа конечного представления
бесконечного языка. Это конечное представление само будет строкой символов
над некоторым алфавитом с подразумеваемой интерпретацией, которая
связывает это конкретное представление с данным языком.
На второй вопрос ответ отрицателен. В следующем параграфе будет
показано, что множество всех предложений над данным словарём счётно-
бесконечно.
То, что множество всех подмножеств счётно-бесконечного множества не
является счётно-бесконечным, есть хорошо известный факт теории множеств
2
.
Другими словами, множество всех языков над данным алфавитом несчётно.
Ясно, что конечное представление языка будет предложением какого-то
(обычно, другого) языка (
метаязыка). Но этот последний, как и любой другой
язык, не более чем счётно-бесконечное множество предложений. Так что
существует значительно больше языков, чем конечных представлений.
Ответу на третий вопрос посвящена бóльшая часть дальнейшего
изложения.
§ 1.2. Представление языков
Распознавание. Один из способов представления языка состоит в том,
чтобы дать
алгоритм
3
, который определяет, есть ли данное предложение в
данном языке или нет.
Более общий способ — дать
процедуру, которая прекращает работу с
ответом “да” для предложений в языке и, либо не завершается
4
, либо
завершается с ответом “нет” для предложений не из языка. Говорят, что такие
алгоритм и процедура
распознают язык.
Существуют языки, которые можно распознать при помощи процедуры, но
не при помощи алгоритма.
Порождение. Другой способ представления языка — дать процедуру,
которая систематически порождает предложения языка последовательно в
некотором порядке.
Если имеется алгоритм или процедура, которые
распознают предложения
языка над алфавитом
V, то на их основе можно построить порождающий
механизм — алгоритм или процедуру,
порождающий этот язык. Именно,
можно систематически генерировать все предложения из множества V
*
,
проверять каждое предложение на принадлежность его языку с помощью
2
Теорема Г. Кантора (1878 г.).
3
Согласно Д. Кнуту [11] алгоритм — это свод конечного числа правил, задающих
последовательность выполнения операций при решении той или иной конкретной задачи. Для
алгоритма характерны следующие пять особенностей: (1) конечность — завершаемость после
выполнения конечного числа шагов; (2) определенность — однозначность; (3) ввод —
исходные данные; (4) вывод — результат; (5) эффективность — выполнимость любой
операции за конечное время. В вырожденных случаях ввод и (или) вывод могут отсутствовать.
4
Этим она и отличается от алгоритма.
Страницы
- « первая
- ‹ предыдущая
- …
- 8
- 9
- 10
- 11
- 12
- …
- следующая ›
- последняя »
