Примеры
- Регулярный язык: $L_{reg}=\{w\in \{a,b{\}}^{\ast }\mid w$ содержит чётное число символов $a\}$ (или проще: регулярное выражение $(b^{\ast }a{b}^{\ast }a{b}^{\ast }{)}^{\ast }$).
- Контекстно‑свободный язык: $L_{cf}=\{a^n{b}^n\mid n\ge 0\}$.
- Не порождаемый КС‑грамматикой (не-КС): $L_{non}=\{a^n{b}^n{c}^n\mid n\ge 0\}$.
Методы доказательства нерегулярности
1. Лемма о накачке для регулярных языков (формулировка): существует число $p$ (порог) такое, что любое слово $s\in L$ с $|s|\ge p$ можно разложить как $s=xyz$ с условиями $|xy|\le p$, $|y|\ge 1$, и для всех $i\ge 0$ слово $x{y}^{i}z\in L$.
Применение (пример): допустим язык $\{a^n{b}^n\}$ регулярный. Пусть $p$ — порог, возьмём $s=a^p{b}^p$. По лемме $s=xyz$ и $y$ состоит только из $a$. Для $i=0$ получаем $xz$ с меньше чем $p$ символами $a$ и $p$ символами $b$ — не в языке. Противоречие → язык не регулярный.
2. Альтернативы/усиления: теорема Майхила–Нерода (количество различимых по префиксам эквивалентных классов бесконечно ⇒ не регулярный) и замыкательные свойства регулярных языков (например, пересечение с регулярным языком даёт регулярный язык) используются для конструктивных доказательств.
Методы доказательства неконтекстно‑свободности
1. Лемма о накачке для КС‑языков (Bar‑Hillel): существует порог $p$ такой, что любое $s\in L$ с $|s|\ge p$ раскладывается как $s=uvwxy$ с $|vwx|\le p$, $|vx|\ge 1$ и для всех $i\ge 0$ слово $u{v}^{i}w{x}^{i}y\in L$.
Применение (пример): предположим $L_{non}=\{a^n{b}^n{c}^n\}$ — КС. Пусть $p$ и возьмём $s=a^p{b}^p{c}^p$. По условию $|vwx|\le p$, значит позиция $vwx$ попадает максимум в две соседние группы символов (не во все три). При накачке $i\ne 1$ числа одной либо двух букв изменятся, а остальные останутся прежними → соотношение $n,n,n$ нарушается → противоречие. Значит $L_{non}$ не КС.
2. Огден (Ogden) — более сильная лемма: можно пометить $p$ позиций так, чтобы образец накачки обязательно затрагивал помечённые позиции; полезна, когда стандартная лемма даёт сложные случаи.
3. Замыкательные свойства: класс КС замкнут относительно пересечения с регулярными языками. Часто берут предполагаемый КС‑язык $L$, пересекают с подходящим регулярным $R$ так, чтобы $L\cap R$ было равным известному не‑КС языку (или вида, для которого можно применить лемму) — и получают противоречие.
Применимость к синтаксическому анализу языков программирования
- Лексический анализ: токены обычно описывают регулярными языками (регулярные выражения, ДКА).
- Синтаксический анализ (парсинг): большая часть синтаксиса языков программирования описывается КС‑грамматиками; для детерминированных КС‑грамматик используются алгоритмы LL(k), LR(k), LALR, GLR и т.п. Эти алгоритмы эффективны и практичны.
- Ограничения: некоторые языковые конструкции по сути контекстно‑чувствительны (например, проверка совпадения объявлений/использований, проверка типов, отступы в Python в некотором смысле) — это решается не расширением формальной грамматики до полной контекстно‑чувствительности, а семантическим анализом, атрибутными грамматиками, либо простыми доп. проверками/предобработкой (либо с помощью механик в PEG, семантических предикатов и т.д.).
Вывод: регулярные языки подходят для лексики; КС‑языки покрывают основную часть синтаксиса и позволяют эффективный парсинг; более сложные свойства языка обычно обрабатывают семантикой и дополнительными механизмами, а не чисто более сильными грамматиками.