Как иерархия Хьюски и машины Тьюринга должны влиять на языковой дизайн? - PullRequest
Новая
       39

Как иерархия Хьюски и машины Тьюринга должны влиять на языковой дизайн?

9 голосов
/ 14 июня 2009

В настоящее время я учусь на дискретный тест по математике, в котором мы изучаем иерархию Хомского и тип автоматов, которые распознают каждый уровень иерархии. Меня учат, что большинство компьютерных языков относятся к «уровням 2 и 1» иерархии, но не совсем так.

Мои вопросы:

  1. Какие функции принадлежат каждому уровню?

  2. Это не более чем теоретическая основа? Мне интересно, должны ли такие дизайнеры, как Деннис Ритчи и Джеймс Гослинг, учитывать эти соображения при разработке C и Java. Они? Как кто-то может применить это?

  3. Нам говорят, что машины Тьюринга распознают уровень 0 иерархии. Если да, есть ли какие-либо языковые функции, относящиеся к уровню 0? Я предполагаю, что это может быть обработка естественного языка, не так ли?

Ответы [ 2 ]

7 голосов
/ 14 июня 2009

  1. Отсутствует. Уровень 1 включает в себя уровень 2. Может быть, я вас неправильно понял, так что для полноты:

    • Обычные языки используются при сопоставлении регулярных выражений. Разговорный: DFA не в счет. И вам нужно посчитать, если вы хотите сопоставить скобки. [Уровень 3]
    • Синтаксис языка обычно является языком без контекста. Смотри 2) [Уровень 2]
    • Контекстно-зависимый язык используется только теоретически. Смотри 3) [Уровень 1]

  2. Помогает в разработке лексеров и парсеров. Я не знаю, думали ли об этом создатели C, но Java, конечно. Генератор парсера

  3. Машины Тьюринга рассчитывают все, что можно рассчитать. «Может быть рассчитано» даже определяется как: Может быть принято машиной Тьюринга. Это включает, конечно, обработку естественного языка. Все, что выше уровня 2, не очень полезно для языковой генерации, потому что программа, читающая такие входные данные, может не останавливаться ( Слово Проблема больше не может быть решена).

3 голосов
/ 14 июня 2009

Грамматика типа 3 генерирует обычные языки. Это языки с такими особенностями, как начинается с «xxx», содержит «xxx», заканчивается «xxx», содержит нечетное число символов y и т. Д. Конечные автоматы (детерминированные или нет) распознают эти языки.

Грамматика типа 2 генерирует языки без контекста. Это языки с такими особенностями, как некоторое количество символов «х», за которыми следует меньше или больше или равное количество символов «у», или где за словом следует то же слово, но в обратном порядке. Автоматы Pushdown распознают эти языки ... представьте, что конечный автомат со стеком.

Грамматика типа 1 генерирует контекстно-зависимые языки. Они настолько близки к грамматике типа 0, что зачастую трудно найти разницу между ними. LBA (линейные ограниченные автоматы) распознают эти языки, думают, что машина Тьюринга с ограниченными ресурсами ... думают, что это современный компьютер.

Грамматики типа 0 генерируют языки тьюринга, которые иногда называют рекурсивно перечислимыми языками. Это в основном любой язык, который вы могли бы написать для распознавания компьютерной программы, но они действительно сочетаются с Типом 1, поскольку реальные компьютеры обычно имеют какой-то предел памяти.

Конечные автоматы и автоматы pushdown очень важны при решении проблем, возникающих при написании компиляторов. Однако, это не то, почему вы изучаете их, вы изучаете их, чтобы узнать пределы того, что можно / нельзя вычислить. Многие программисты считают, что вы можете решить любую проблему с помощью компьютера. Теория вычислимости учит вас иначе.

Редактирование "Dude" - хорошо, вот простая (и известная) проблема, которую не может решить ни машина Тьюринга, ни компьютер, ни программист, ни инопланетный гений ...

Представьте, что у вас есть несколько домино ... но вместо шаблонов точек у вас есть короткое слово сверху и снизу, скажем, такие слова, как "аба" и "такси". Если я дам вам 5, 10 или 50 таких домино, можете ли вы расположить их так, чтобы слова сверху, все соединенные вместе, точно совпали со словами внизу? Вы можете сделать столько копий, сколько захотите, для каждого домино.

Пример домино (надуманный :) (a / aab), (aba / ac), (cab / ab) - это набор из 3 домино, где вершины (a + aba + cab) точно равны основаниям (aab + ac + аб).

Как бы легко это ни звучало, это не может быть решено вообще.

Кстати, когда я впервые прочитал / понял эту проблему ... я думал ... ооооо, n! начинает хорошо выглядеть!

...