Я читал о Йоте и Джоте и нашел этот раздел запутанным:
В отличие от Iota, где синтаксическое дерево для строки может разветвляться либо слева, либо справа, синтаксис Jot равномерно разветвляется слева. В результате, Йота не зависит от контекста, но Йот - это обычный язык.
Насколько я понимаю, и Йота, и Йот завершены по Тьюрингу. Но, по-видимому, один не зависит от контекста, а другой является регулярным! Конечно, обычные языки не могут быть полными по Тьюрингу?
1*0
что это обычный язык ;-) Хотя это и не очень дружественный язык программирования ни для программиста, ни для разработчика компилятора.Ответы:
Короче говоря, ответ - да.
Но вы смешиваете два совершенно не связанных значения термина «язык» (да, это сбивает с толку):
Обратите внимание, что вы можете говорить о «языке C ++» с двух совершенно не связанных точек зрения, используя два несвязанных значения слова «язык»:
Черты «языка C ++» с этих двух точек зрения не связаны.
Дополнительные примеры, которые помогут вам отделить эти понятия:
источник
(([a-z][0-9]*)*[A-Z][0-9]*([a-z][0-9]*)*->([a-zA-Z][0-9]*)*)*
это обычный язык, который может описывать грамматику любого языка класса 0,В то время как набор юридических программ в Jot является регулярным, сам Jot завершается по Тьюрингу. Это означает, что каждая вычислимая функция может быть выражена в Jot. Мы даже можем придумать язык, на котором все двоичные строки допустимы, но сам язык является полным по Тьюрингу (упражнение). Вы путаете синтаксис и семантику.
Кстати, контекстно-свободные языки также (вероятно) не являются NP-полными, поскольку имеют алгоритм синтаксического анализа за полиномиальное время.
источник
Один только синтаксис (как закодировано в деревьях синтаксиса) современных языков программирования далек от всего, что они делают. Фактически формальные языки, определяемые набором всех программ на данном языке, которые компилируются без ошибок, редко бывают даже контекстно-свободными .
Статический и динамический фактор семантики в уравнении. Они невидимы в синтаксическом дереве, но определяют, является ли фрагмент кода программой и что он вычисляет. Итог, без контекста соотв. регулярный формальный язык, который определяется «синтаксисом», дает избыточное приближение языка программирования.
Теперь, чтобы ответить на ваш вопрос: да, это возможно. Рассмотрим, например, любую геделевскую нумерацию машин Тьюринга; Вы получаете «язык программирования» всех натуральных чисел, каждое из которых представляет ТМ. Конечно, это не очень хороший язык для программирования, но это, конечно, полный по Тьюрингу язык, который является обычным - даже тривиальным.
источник
Язык программирования полон по Тьюрингу, если он достаточно выразителен, чтобы указывать каждую функцию, вычислимую на машинах Тьюринга. Здесь мы обсуждаем силу языков, указанных в языках программирования . Например, нетрудно написать интерпретатор для машин Тьюринга в Python, поэтому Python является языком программирования, полным по Тьюрингу.
Синтаксис языка программирования , то есть набора строк, соответствующих действительным программам на языке программирования, сам является языком. Например, рассмотрим множество всех возможных программ Python. Синтаксис языка программирования может быть контекстно-зависимым , контекстно-свободным , обычным и т. Д. Нас интересует сложность проверки того, что данная строка является допустимой программой на языке программирования (это делают компиляторы / интерпретаторы). Когда мы говорим, что синтаксис языка программирования не зависит от контекста, это означает, что для его синтаксиса существует не зависящая от контекста грамматика, и подразумевается, что есть автомат для проверки правильности программ,
Обратите внимание, что простота синтаксиса языка программирования не подразумевает ограничения вычислительной мощности программ, указанных на этих языках программирования.
источник
Ответ - да. Видите ли, как говорится в принятом ответе, грамматика не зависит от ее значения. По словам самого Хомского:
Если грамматика может дать достаточно предложений для описания всех вещей, которые могут быть вычислены, то мы можем произвольно назначать вычислительные значения ее предложениям - по одному для каждой вещи, которая может быть вычислена.
Что касается реального конкретного примера, популярный язык
whitespace
имеет регулярную грамматику и, возможно, дажеx86 assembly languages
(нуждается в проверке).источник