Кратко: язык $L(G)$ — все палиндромы над алфавитом $\{a,b\}$:
$$L(G)=\{w\in \{a,b{\}}^{\ast }\mid w=w^R\}.$$
Класс языка:
- Контекстно-свободный: грамматика задана явно (правила $S\to aSa\mid bSb\mid a\mid b\mid \epsilon$).
- Не регулярный. Доказательство (пьз. леммы о накачке для регулярных языков): пусть $p$ — длина накачки; выберем
$$s=a^{p}b{a}^p\in L.$$ По лемме $s=xyz$, $|xy|\le p$, $|y|>0$. Тогда $y=a^k$ для некоторого $k>0$. Для $i=0$ получаем
$$xz=a^{p-k}b{a}^p,$$ что не палиндром — противоречие. Следовательно $L$ не регулярный.
- Рекурсивный (разрешимый) и, разумеется, перечислимый; также язык относится к контекстно-чувствительным языкам.
Автомат/грамматика более низкой сложности:
- Никакой конечный автомат не существует (см. нерегулярность), т.е. язык нельзя описать регулярной грамматикой. Поэтому по сложности класс ниже (регулярный) невозможен.
NPDA (словоописание): ненаблюдаемый магазинный автомат делает либо
1) на входе пушит символы $a$ или $b$ на стек; в любой момент может переходом по $\epsilon$ перейти в фазу сравнения, после чего при чтении каждого символа поп-операцией проверяет соответствие верхушки стека и символа и делает pop; принимает, если вход закончился и стек пуст (или содержит только начальный маркер). Это стандартный недетерминированный PDA для палиндромов.
Алгоритм разбора и сложность:
- Общие синтаксические алгоритмы для КС-грамматик: CYK — $O(n^3)$ (после приведения в Хомский НФ), Earley/GLR — в худшем случае $O(n^3)$.
- Для этого конкретного языка существует простая линейная проверка: сравнивать $s[i]$ и $s[n-1-i]$ для всех $i=0,\dots ,\lfloor (n-1)/2\rfloor$. Это даёт детерминированную проверку за $O(n)$ времени (и $O(1)$ дополнительной памяти при доступе к символам по индексу) или за $O(n)$ времени и $O(n)$ памяти при реализации через стек в двух проходах (сначала узнать $n$, затем пушить первые $\lfloor n/2\rfloor$ символов и сравнивать остаток).
- Замечание: общий детерминированный PDA (однопроходный, без возможности обратного чтения) для этого языка не даётся; поэтому в теории язык записывают как НПДА/КС-грамматику, но практическая проверка палиндрома реализуется линейным алгоритмом, описанным выше.
Итого: $L(G)$ — контекстно‑свободный, не регулярный, разрешимый; проверка принадлежности может быть выполнена за $O(n)$ времени на практике, общие парсеры для произвольной КС‑грамматики — за $O(n^3)$ в худшем случае.