Язык и его описание:
- Грамматика: $S\to aSb\mid SS\mid \epsilon$.
- Язык $L$ порождаемый этой грамматикой — это язык корректно вложенных пар «$a$» и «$b$» (аналог скобочной последовательности одного типа):
$$L=\{w\in \{a,b{\}}^{\ast }\mid \text{для любой префикс-строки}u\text{имеем}|u{|}_a\ge |u{|}_b\text{и}|w{|}_a=|w{|}_b\}.$$
Позиция в иерархии Хомского:
- Это контекстно-свободный язык (тип‑2).
- Он не является регулярным: например
$$L\cap a^{\ast }{b}^{\ast }=\{a^n{b}^n\mid n\ge 0\},$$ а множество $\{a^n{b}^n\}$ нерегулярно, значит и $L$ нерегулярен.
- Более того $L$ — детерминируемый КС-язык (детерминируемый CFL).
Однозначность грамматики:
- Данная грамматика $S\to aSb\mid SS\mid \epsilon$ неоднозначна. Пример неоднозначности: строка $ababab$ (три пары) имеет разные разбиения на две части при применении правила $S\to SS$, что даёт разные деревья вывода (разные ассоциативные скобления).
- Однако язык сам по себе не является внутренне неоднозначным: существует нековарьированная (однозначная) грамматика для того же языка, например
$$S\to aSbS\mid \epsilon ,$$ которая задаёт уникальную декомпозицию (можно доказать единственность вывода по индукции), поэтому язык допускает однозначную грамматику.
Детерминированный магазинный автомат (DPDA):
- Можно построить детерминированный МП‑автомат, который распознаёт $L$. Простейшая конструкция — один рабочий состояние $q$, маркер низа стека $Z_0$ и символ стека $A$ для незакрытых «$a$»:
$$\begin{array}{rl}& \delta (q,a,Z_0)=(q,A{Z}_0),\delta (q,a,A)=(q,AA),\\ & \delta (q,b,A)=(q,\epsilon ).\end{array}$$ Перехода на $b$ при $Z_0$ нет (тогда автомат отвергает). Автомат принимает по пустому стеку (или по состоянию при пустом стеке). Это детерминированный МП‑автомат, он корректно пушит при встрече $a$ и попит при $b$, не требуя нелокального угадывания, и распознаёт ровно $L$.
Краткое резюме:
- Язык: корректно вложенные последовательности $a$/$b$.
- Хомский: тип‑2 (контекстно‑свободный), не регулярный, детерминируемый КС.
- Грамматика заданная в условии неоднозначна; язык имеет однозначную грамматику (напр. $S\to aSbS\mid \epsilon$).
- Существует DPDA, приведён выше.