Кратко и по пунктам.
1) Язык и класс
- Язык $L(G)=\{a^n{b}^n\mid n\ge 0\}$.
- Это контекстно-свободный язык (более того — детерминированно КС-язык, DCFL), но не регулярный.
2) Pushdown Automaton (формально)
- $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,Z_0,F)$, где
$Q=\{q_0,q_1,q_f\},\Sigma =\{a,b\},\Gamma =\{A,Z_0\},F=\{q_f\}.$ - Набор переходов $\delta$ (запись в виде множеств образов):
$$\begin{array}{rl}& \delta (q_0,a,Z_0)\ni (q_0,A{Z}_0),\\ & \delta (q_0,a,A)\ni (q_0,AA),\\ & \delta (q_0,b,A)\ni (q_1,\epsilon ),\\ & \delta (q_1,b,A)\ni (q_1,\epsilon ),\\ & \delta (q_0,\epsilon ,Z_0)\ni (q_f,Z_0),\delta (q_1,\epsilon ,Z_0)\ni (q_f,Z_0).\end{array}$$ - Идея: в состоянии $q_0$ считываем $a$ и пушим маркер $A$; при первом $b$ переходим в $q_1$ и для каждого $b$ попем по одному $A$. Пустая строка принимается переходом в $q_f$ при неповреждённом $Z_0$.
3) Доказательство нерегулярности (прамма регулярных языков)
- Пусть язык регулярный. По лемме о накачке существует число $p$ (параметр накачки).
- Возьмём строку $s=a^p{b}^p\in L$. По лемме $s=xyz$ такие, что $|xy|\le p$ и $|y|>0$. Тогда $y$ состоит только из символа $a$ (поскольку первые $p$ символов — все $a$).
- По лемме строка $x{y}^{0}z=xz$ должна принадлежать языку. Но $xz$ содержит меньше чем $p$ символов $a$ и всё ещё $p$ символов $b$, то есть имеет вид $a^{p-|y|}{b}^p$ и не лежит в $L$. Противоречие. Следовательно язык не регулярный.
4) Преобразование грамматики в нормальную форму Хомского (CNF)
Исходная грамматика:
$$S\to aSb\mid \epsilon .$$ Шаги (коротко):
- Введём новый стартовый символ $S_0$ и сохраним пустую строку: $S_0\to S\mid \epsilon$.
- Удаляем $\epsilon$-правило из $S$. Поскольку $S$ nullable, из $S\to aSb$ получаем дополнительно $S\to ab$. Получаем:
$$S\to aSb\mid ab.$$ - Заменим терминалы в правых частях длиннее 1 на нетерминалы: введём $A\to a,B\to b$, тогда
$$S\to ASB\mid AB.$$ - Преобразуем правила длины >2 в бинарные, введя новый нетерминал $X$ для $SB$:
$$X\to SB,S\to AX\mid AB.$$ - Устраняем единичные продукции у $S_0$: заменяем $S_0\to S$ продукциями $S$, получаем окончательно (и допускаем $S_0\to \epsilon$ как единственное $\epsilon$-правило для стартового символа):
$$\begin{array}{rl}& S_0\to AX\mid AB\mid \epsilon ,\\ & S\to AX\mid AB,\\ & X\to SB,\\ & A\to a,B\to b.\end{array}$$ - Все правые части сейчас либо два нетерминала, либо одиночный терминал (и единственное $\epsilon$-правило — у стартового символа), поэтому это CNF-форма эквивалентной грамматики.
Конец.