Кратко: язык порождаемый грамматикой $S\to aSb\mid \epsilon$ равен
$$L=\{a^n{b}^n\mid n\ge 0\},$$ он не регулярный, поэтому не существует ни ДКА, ни НКА, распознающего этот язык. Зато существует магазинный автомат (PDA). Докажу это и приведу PDA.
1) Нерегулярность (доказательство через лемму о накачке).
Пусть для противоречия $L$ регулярный; пусть $p$ — длина накачки. Возьмём строку
$$s=a^p{b}^p.$$ По лемме $s=xyz$, где $|xy|\le p$, $|y|>0$. Тогда $y$ состоит только из символов $a$, скажем $y=a^k$, $k>0$. Накочивая $i=0$ получаем
$$xz=a^{p-k}{b}^p,$$ что не принадлежит $L$ (число $a$ меньше числа $b$). Противоречие. Значит $L$ не регулярен.
2) PDA, распознающий $L$.
Опишем детерминированный PDA $M=(\{q\},\{a,b\},\{Z_0,A\},\delta ,q,Z_0,\varnothing )$ с принятием по переходу в особое финальное состояние (или по финальному состоянию). Можно сократить до приёма по пустому стеку; ниже даётся вариант с финальным состоянием $q_f$.
Переходы (в виде $\delta (\text{состояние},\text{символ входа},\text{символ на стеке})\ni (\text{новое состояние},\text{замена на стеке})$):
- Для каждого прочитанного $a$ пушим метку $A$:
$$\delta (q,a,Z_0)\ni (q,A{Z}_0),\delta (q,a,A)\ni (q,AA).$$ - Для каждого прочитанного $b$ попаем одну $A$:
$$\delta (q,b,A)\ni (q,\epsilon ).$$ - Когда вход прочитан и на стеке только $Z_0$, делаем $\epsilon$-переход в финальное состояние:
$$\delta (q,\epsilon ,Z_0)\ni (q_f,Z_0).$$
Интуиция и корректность: при чтении $a^n$ автомат запишет $n$ символов $A$ на стек; при последующем чтении $b$ каждый символ $b$ удаляет ровно одну $A$. Строка принимается тогда и только тогда, когда после обработки всего ввода стек вернулся к $Z_0$ (т.е. число $b$ равно числу ранее прочитанных $a$). Далее по индукции видно, что $M$ принимает ровно строки $a^n{b}^n$.
3) Можно ли преобразовать грамматику в регулярную?
Нет. Регулярная грамматика порождает регулярный язык; поскольку $L=\{a^n{b}^n\}$ не регулярен, никакой регулярной грамматики, эквивалентной данной, не существует. Также непосредственно видно, что правило $S\to aSb$ не является ни праволинейным, ни леволинейным (рекурсивный символ находится в середине продукции), так что прямое приведение к регулярной форме невозможно.
Вывод: НКА/ДКА для данного языка не существует; корректный автомат — PDA, приведённый выше; грамматику в регулярную преобразовать нельзя, потому что язык нерегулярен.