1) Регулярность языка L = { a^n b^n | n ≥ 0 }

Докажем, что L не регулярный, используя лемму о накачке для регулярных языков.

Пусть, для противоречия, L регулярный. Тогда существует число p $длина«накачки»$ из леммы. Возьмём строку
s = a^p b^p ∈ L,
и разложение s = x y z, удовлетворяющее условиям леммы:
|xy| ≤ p и |y| ≥ 1.

Поскольку |xy| ≤ p, подстрока y состоит только из символа 'a' $т.к.первыеpсимволовs—вс{е}^{\prime }{a}^{\prime }$. Пусть y = a^k, k ≥ 1. По лемме строка x z = a^{p-k} b^p должна принадлежать L. Но в xz число символов 'a' равно p−k, а число 'b' равно p, то есть они не равны, следовательно xz ∉ L — противоречие. Значит исходное предположение неверно и L не регулярный.

2) КС-грамматика для L

Контекстно-свободная грамматика, порождающая ровно L:

S → a S b | ε

Доказательство корректности: правило S → a S b увеличивает одновременно число 'a' слева и 'b' справа, а S → ε даёт базовый случай n = 0. По индукции получаем все строки a^n b^n и только их.

3) Автомат с магазинной памятью $PDA$ для L

Ниже даются два варианта: нерегулярный $односостояние,приёмпопустомустеку$ и детерминированный $несколькосостояний,приёмпофинальномусостоянию$.

a) Нерегулярный NPDA $приёмпопустомустеку$

M = $q,\Sigma =a,b,\Gamma =A,Z0,q,Z0,\varnothing$, δ:

δ$q,a,Z0$ ⊇ {$q,AZ0$}δ$q,a,A$ ⊇ {$q,AA$}δ$q,b,A$ ⊇ {$q,\epsilon$}δ$q,\epsilon ,Z0$ ⊇ {$q,\epsilon$} $чтобывконцеможнобылоудалитьначальныймаркериполучитьпустойстек$

Работа: читаем первые a и для каждой a кладём в стек символ A. При первых b начинаем для каждого b снимать по одному A. Если число a равно числу b, в конце стек очистится $вместесZ0$, и автомат примет.

b) Детерминированный PDA $приёмпофинальномусостоянию$

M = $q0,q1,qf,\Sigma =a,b,\Gamma =A,Z0,q0,Z0,qf$, δ:

δ$q0,a,Z0$ = $q0,AZ0$δ$q0,a,A$ = $q0,AA$δ$q0,b,A$ = $q1,\epsilon$δ$q1,b,A$ = $q1,\epsilon$δ$q1,\epsilon ,Z0$ = $qf,Z0$

Идея: в состоянии q0 читаем и пушим все a; при первом b переводимся в q1 и начинаем попить A для каждого b; если вход закончился и в стеке остался только маркер Z0, делаем ε-переход в принимающее состояние qf. Этот автомат детерминированен $вкаждойситуациинетнеоднозначныхпереходов$.

4) Практические применения КС-языков

Синтаксический анализ языков программирования: большинство синтаксисов $сбалансированныескобки,вложенностьблоков,конструкцииif/while/\dots$ описываются КС-грамматиками; парсеры $LL,LR,LALRит.п.$ реализуют детерминированные КС-автоматы.Обработка и проверка структурированных документов: XML/HTML $правильноевложениетегов$, некоторые форматы данных.Разбор арифметических выражений $приоритеты,ассоциативность$ и построение деревьев разбора.Верификация и анализ протоколов и систем с вложенной структурой $моделированиестековойпамятиввызовах,возвратах$.Инструменты статического анализа кода $парсинг,построениеAST$.Некоторые задачи обработки естественного языка $фрагментысинтаксисаможноописатьКС-грамматиками$.

Ограничения и замечания:

КС-языки сильнее регулярных, но слабее контекстно-зависимых — например, язык { a^n b^n c^n | n ≥ 0 } не является КС.Для практических парсеров важна детерминированность грамматики $чтобыиметьэффективныелинейныепарсеры:LL(k),LR(k)$, а многие КС-грамматики бывают амбигвными $несколькодеревьевразборадляоднойстроки$.КС-грамматики хорошо подходят для описания вложенной структуры, но недостаточны, когда нужны перекрёстные зависимости между несколькими счётчиками $требуетсяболеемощнаямодель$.

Краткий итог: L = { a^n b^n } не регулярный, но контекстно-свободный; его легко задать грамматикой S → a S b | ε и реализовать простым $детерминированным$ стековым автоматом. Контекстно-свободные языки широко применяются для описания и разбора вложенных структур в программировании и обработке данных.