Кратко: грамматика
S → a S b | S S | ε
порождает язык правильных $сбалансированных$ скобочных строк, где «a» = «$»,«b»=«$» $Dyck‑языксоднимтипомскобок$. Грамматика неоднозначна, язык является контекстно‑свободным, не регулярным, но распознаётся детерминированным магазинным автоматом $т.е.этодетерминированныйКС‑язык$.

Развёрнуто:

1) Описание языка L$G$

L$G$ = { w ∈ {a,b}* | в каждой префиксной части w число a ≥ число b, и в целом число a = число b }.Иными словами — все корректно сбалансированные строки вида комбинаций пар a...b, т.е. классический Dyck‑язык с одной парой скобок.

2) Неоднозначность грамматики
Грамматика неоднозначна. Пример: строка "ab".
Два различных вывода:

S ⇒ a S b ⇒ a ε b = "ab"S ⇒ S S ⇒ $aSb$ S ⇒ $a\epsilon b$ ε = "ab"
Оба вывода дают разные деревья разбора, значит грамматика неоднозначна.

3) Построение автомата $детерминированныймагазинныйавтомат$ НКА/ДКА не подойдёт, язык не регуляр, но можно построить простой детерминированный МПА, который считывает символы слева направо, на каждом 'a' кладёт маркер в стек, на каждом 'b' — снимает маркер; если попытка снять при пустом стеке — отклоняет. При конце входа автомат принимает тогда и только тогда, когда стек пуст $кромедна$.

Формальное описание $одноставовыйдетерминированныйМПА,принимающийпопустомустеку$:

Q = {q}, Σ={a,b}, Γ={Z, X} $Z—символдна$, q0=q, нач. стек = Z.Переходы δ:
δ$q,a,Z$ = $q,XZ$δ$q,a,X$ = $q,XX$δ$q,b,X$ = $q,\epsilon$ $поп$нет перехода δ$q,b,Z$ $т.е.прилишнейbавтоматотклоняет$Принимает, если на конце входа стек равен Z $пуст,кромедна$.

Это детерминированно: для каждой комбинации $символ,верхстека$ не более одного перехода.

4) К какому типу формальных языков относится L$G$ и почему

L$G$ — контекстно‑свободный язык $порождаетсяКС‑грамматикой$.L$G$ не является регулярным. Доказательство стандартно через лемму о накачке: пусть p — константа накачки, возьмём s = a^p b^p ∈ L. Любое разбиение s = xyz с |xy| ≤ p, |y| > 0 даёт y состоящее только из a. При i = 0 получим xz с меньшим числом a, чем b, следовательно xz ∉ L — противоречие.L$G$ на самом деле детерминированно контекстно‑свободен $Dyc{k}_1$. Для него существует детерминированный МПА $каквыше$, значит язык принадлежит множеству детерминированных КС‑языков $DCFL$. Замечание: хотя язык DCFL, данная грамматика S → a S b | S S | ε сама неоднозначна; для языка существуют и однозначные/детерминированные описания $напримеравтомат$.

Если нужно, могу:

привести простую неоднозначность для более длинной строки (например "abab"),или записать детерминированный МПА в другом формальном формате $таблицапереходов$,или дать неформальную визуализацию дерева разбора и объяснить, как получить однозначную грамматику.