Как Иерархия Chomsky и Машины Тьюринга должны влиять на дизайн языка?
В моем случае решение было так же просто, как закрыть окно браузера, открыть новое и перезагрузить ваш проект. Ошибка появляется только после того, как я перезагружаю свой проект в одном и том же окне более 16 раз.
2 ответа
Нет. Уровень 1 включает Уровень 2. Возможно, я вас неправильно понял, поэтому для полноты:
- Регулярные языки используются в рамках согласования регулярных выражений. Разговорный: DFA не могут считаться. И вам нужно посчитать, если вы хотите сопоставить скобки. [Уровень 3]
- Синтаксис языка обычно является контекстно-свободным языком. См. 2) [Уровень 2]
- Контекстно-зависимый язык используется только теоретически. См. 3) [Уровень 1]
Помогает в разработке лексеров и синтаксических анализаторов. Не знаю, думали ли об этом создатели C, но Java, конечно. Генератор синтаксического анализатора
Машины Тьюринга вычисляют все, что можно вычислить. «Может быть вычислено» даже определяется как: Может быть принято машиной Тьюринга. Это включает, конечно, обработку естественного языка. Все, что выше уровня 2, не очень полезно для генерации языков, потому что программа, считывающая такие входные данные, может не останавливаться ( Проблема Word больше не может быть решена).
Грамматики типа 3 генерируют регулярные языки. Это языки с такими функциями, как начало с «ххх», содержит «ххх», заканчивается на «ххх», содержит нечетное число y и т. Д. Конечные автоматы (детерминированные или недетерминированные) распознают эти языки.
Грамматики типа 2 генерируют контекстно-свободные языки. Это языки с такими функциями, как некоторое количество x, за которым следует меньшее, или большее или равное количество y, или где за словом следует то же слово, но в обратном порядке. Автоматические опускающиеся вниз автоматы распознают эти языки ... думайте, что конечный автомат со стеком.
Грамматики типа 1 генерируют контекстно-зависимые языки. Они настолько близки к грамматикам типа 0, что часто бывает трудно найти разницу между ними. LBA (линейные ограниченные автоматы) распознают эти языки, подумайте о машине Тьюринга с ограниченными ресурсами ... подумайте о современном компьютере.
Грамматики типа 0 порождают языки Тьюринга, иногда называемые рекурсивно перечисляемыми языками. По сути, это любой язык, на котором вы могли бы написать компьютерную программу для распознавания, но они действительно сочетаются с типом 1, поскольку у реальных компьютеров обычно есть какой-то предел памяти.
Конечные автоматы и автоматы выталкивания очень важны в решении проблем, которые возникают при написании компиляторов. Однако вы изучаете их не поэтому, вы изучаете их, чтобы узнать пределы того, что можно / нельзя вычислить. Многие программисты думают, что с помощью компьютера можно решить любую проблему. Теория вычислимости учит вас обратному.
Редактировать "Dude" - Хорошо, вот простая для понимания (и известная) проблема, которую не может решить ни одна машина Тьюринга, компьютер, программист или инопланетный гений ...
Представьте, что у вас есть домино ... но вместо узоров из точек у вас есть некоторые короткие слова сверху и снизу, произнесите такие слова, как «aba» и «cab». Если я дам вам 5, 10 или 50 таких домино, можете ли вы расположить их так, чтобы слова наверху, все сцепленные вместе, точно совпадали со сложенными словами внизу. Вы можете сделать сколько угодно копий каждого домино.
Пример домино (придумано :) (a / aab), (aba / ac), (cab / ab) представляет собой набор из 3 костяшек домино, у которых вершины (a + aba + cab) в точности равно основанию (aab + ac + ab).
Как бы просто это ни звучало, это не может быть решено в целом.
Кстати, когда я впервые прочитал / понял эту проблему. .. я думал .... ооооо, н!