Кратко и по делу.
Определения
- Контекстно‑свободные языки (КСЯ): это множества строк, порождаемые контекстно‑свободными грамматиками (CFG) или распознаваемые ненаправленными магазинными автоматами (PDA). Формально: язык L — КСЯ, если существует CFG G такой, что $L=L(G)$.
- Рекурсивно перечислимые языки (РЯ, semi‑decidable / RE): это множества, распознаваемые детерминированной или недетерминированной машиной Тьюринга, которая для строк из языка остановится и примет, а для строк не из языка может либо отвергнуть, либо не останавливаться. Формально: $L$ — РЯ, если существует МТ $M$ с $L=\{w\mid M\text{принимает}w\}$.
Основные различия
- Мощность/экспрессивность: множество РЯ строго шире множества КСЯ. Примеры языков вне КСЯ, но в РЯ: $\{a^n{b}^n{c}^n\mid n\ge 0\}$ и языки, связанные с поведением машин Тьюринга, например $\{⟨M,w⟩\mid M\text{принимает}w\}$.
- Модель вычислений: КСЯ — PDA/CFG (ограниченная память стеком); РЯ — полноценная МТ (неограниченная память).
- Решаемость (decision problems):
- Для КСЯ задача вхождения (membership) разрешима за полином (например CYK $O(n^3)$; для многих подклассов — за $O(n)$), задача пустоты языка, задача вывода и др. решаемы.
- Для РЯ задача вхождения полуприводима: если $w\in L$, МТ может остановиться и принять; если $w\notin L$, МТ может не остановиться — значит в общем случае задача неразрешима (не существует алгоритма, который всегда ответит да/нет). Множество РЯ не замкнуто относительно дополнения (дополнение РЯ — не обязательно РЯ); только если и РЯ, и его дополнение — РЯ, язык будет рекурсивным (разрешимым).
- Замкнутость по операциям: КСЯ замкнуты под объединением, конкатенацией, звёздой, гомоморфизмами; не замкнуты под пересечением и дополнением. РЯ замкнуты под объединением, пересечением и конкатенацией, но не под дополнением в общем.
- Поведение алгоритмов/парсинга: для КСЯ существуют эффективные алгоритмы парсинга и детерминированные подклассы (LR, LL) для практических языков. Для РЯ распознавание может не завершиться для отрицательных примеров.
Примеры задач в информатике, требующих мощности РЯ (или ведущих к РЯ/неразрешимым языкам)
- Проблема останова (HALT): $\{⟨M,w⟩\mid M\text{останавливается на}w\}$ — классический РЯ‑язык; её дополнение не РЯ.
- Проблема приёма: $\{⟨M,w⟩\mid M\text{принимает}w\}$ — RЕ‑полная.
- Проверка свойств произвольных программ: проверка, останавливается ли программа на всех входах, проверка эквивалентности двух произвольных программ, проверка отсутствия ошибок в общем случае — в общем неразрешимы (сводимы к HALT).
- Проверка достижимости в системах с неограниченной памятью (например, обобщённые Petri-сети, модели с рекурсией и динамической аллокацией) — часто приводят к РЯ‑или даже к неразрешимым проблемам.
- Автоматическое доказательство теорем для общих формул (теорема о полной вычислимости) — распознавание правильных доказательств — РЯ, но проверка тавтологичности некоторых классов формул может быть неразрешима.
Практическая значимость различия
- Языки программирования и синтаксический разбор: в практике используют (детерминированные) КС‑подклассы (LR, LL) — это обеспечивает эффективный и предсказуемый парсинг. Таким образом большинство задач разбора решаются в рамках КСЯ.
- Анализ программ и верификация: многие интересующие свойства программ требуют мощности Тьюринговой машины. Это означает, что в общем случае проверки либо не разрешимы, либо только полуразрешимы — поэтому в практике применяются приближённые методы: ограничение модели (ограничение памяти/глубины), абстрактная интерпретация (консервативные приближения), bounded model checking, эвристики, пользовательские аннотации, интерактивные доказательства.
- Проектирование инструментов: знание, что задача приводит к РЯ/неразрешима, диктует выбор подхода — искать полные решения только в подзадачах (ограниченные классы), либо давать полуавтоматические/итерационные инструменты, выдающие гарантированные, но возможно консервативные ответы.
- Безопасность и тестирование: многие автоматические проверки уязвимостей редуцируются к проблемам, близким к РЯ; практические решения используют статические анализы с ограничениями или динамический анализ.
Вывод (сжатый)
- КСЯ — менее выразительны, но имеют решаемые задачи и эффективный парсинг; РЯ — максимально выразительны в рамках вычислимости, но порождают полуразрешимые или неразрешимые задачи. Практически: синтаксис — КСЯ; сложный программный анализ и верификация часто требуют инструментов, эквивалентных по мощи РЯ, поэтому в реальных системах применяют приближения, рестрикции и эвристики.