Неограниченная грамматика
-
Определение неограниченных грамматик
- Неограниченные грамматики — это грамматики без ограничений, кроме того, что левая часть каждого правила не должна быть пустой.
- Они могут генерировать рекурсивно перечислимые языки.
-
Формальное определение
- Неограниченная грамматика состоит из конечного множества нетерминальных и терминальных символов, конечного множества правил и стартового символа.
- Правила могут быть произвольными, без реальных ограничений.
-
Эквивалентность машинам Тьюринга
- Неограниченные грамматики соответствуют рекурсивно перечислимым языкам, что означает, что для каждой грамматики существует машина Тьюринга, распознающая ее язык.
- Машина Тьюринга для грамматики может быть сконструирована как недетерминированная машина с двумя лентами.
-
Вычислительные свойства
- Проблема определения того, может ли строка быть сгенерирована заданной грамматикой, эквивалентна проблеме остановки, которая является неразрешимой.
- Рекурсивно перечислимые языки закрыты под определенными операциями, но не под различием.
-
Универсальная грамматика
- Эквивалентность неограниченных грамматик и машин Тьюринга подразумевает существование универсальной грамматики, способной распознавать языки других грамматик.
- Это позволяет теоретически создать язык программирования на основе неограниченных грамматик.
-
Дополнительные сведения
- Упоминаются лямбда-исчисление и полуавтоматические системы, а также записи как связанные темы.
Полный текст статьи: