Вопрос #1578675
Дана контекстно-свободная грамматика G: S -> aSa | bSb | a | b | ε. Определите класс языка L(G): регулярный/контекстно-свободный/декурсивный и т.д.; докажите (или опровергните) регулярность языка, предложите автомат или грамматику более низкой сложности, если это возможно, и опишите алгоритм разбора (вид парсера) и сложность разбора строки длины n
\[
L(G)=\{w\in\{a,b\}^*\mid w=w^R\}.
\]
Класс языка:
- Контекстно-свободный: грамматика задана явно (правила \(S\to aSa\mid bSb\mid a\mid b\mid\varepsilon\)).
- Не регулярный. Доказательство (пьз. леммы о накачке для регулярных языков): пусть \(p\) — длина накачки; выберем
\[
s=a^p b a^p\in L.
\]
По лемме \(s=xyz\), \(|xy|\le p\), \(|y|>0\). Тогда \(y=a^k\) для некоторого \(k>0\). Для \(i=0\) получаем
\[
x z=a^{p-k} b a^p,
\]
что не палиндром — противоречие. Следовательно \(L\) не регулярный.
- Рекурсивный (разрешимый) и, разумеется, перечислимый; также язык относится к контекстно-чувствительным языкам.
Автомат/грамматика более низкой сложности:
- Никакой конечный автомат не существует (см. нерегулярность), т.е. язык нельзя описать регулярной грамматикой. Поэтому по сложности класс ниже (регулярный) невозможен.
NPDA (словоописание): ненаблюдаемый магазинный автомат делает либо
1) на входе пушит символы \(a\) или \(b\) на стек; в любой момент может переходом по \(\varepsilon\) перейти в фазу сравнения, после чего при чтении каждого символа поп-операцией проверяет соответствие верхушки стека и символа и делает 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)\,\) в худшем случае.