Ваша грамматика верна. Вот доказательство.
Сначала мы покажем, что ваша грамматика генерирует только строки с одинаковым числом a и b. Обратите внимание, что все производства с S на LHS вводят равное количество A, как они делают B. Следовательно, любая строка терминалов, полученных из S, будет иметь равное количество a и b.
Далее мы покажем, что все строки a и b могут быть получены с использованием этой грамматики. Мы продолжаем использовать математическую индукцию.
Базовый случай: S -> e и оба S -> SASBS -> ASBS -> aSBS -> aBS -> abS -> ab и S -> SBSAS -> BSAS -> bSAS -> bAS -> baS -> ba, поэтому три самые короткие строки в языке генерируются грамматикой. Других строк на языке, длина которых меньше 4.
нет
Гипотеза об индукции: все строки длиной до 2k в языке генерируются грамматикой.
Индуктивный шаг: мы должны показать, что все строки длины 2 (k + 1) на языке также генерируются грамматикой. Если w = axb или w = bya для некоторых строк x и y, то x и y являются строками длины 2k в языке и, следовательно, генерируются грамматикой. В этом случае мы можем использовать тот же вывод с дополнительным применением либо S -> SASBS -> ASBS -> aSBS -> aSbS -> aSb или S -> SBSAS -> BSAS -> bSAS -> bSaS -> bSa и затем используйте вывод для x или y, чтобы завершить вывод, получая w. Если вместо этого w = axa или w = byb, то x или y - это строка с ровно на два больше b, чем a или a, чем b. В этом случае должен быть префикс p для w с | p | <| ш | такой, что p также является строкой в языке (см. лемму ниже). Если префикс p является словом в языке и w = pr, тогда r также должен быть словом в языке, поэтому w должно быть объединением двух слов в L. Эти слова имеют длину меньше, чем | w | поэтому меньше 2 (k + 1) и генерируется грамматикой. Если они генерируются грамматикой, то они имеют форму SaSbS или SbSaS, и их конкатенация может быть получена с использованием грамматики с использованием произведений в правильной последовательности. То есть S -> SASBS -> SASBSBSAS -> aSbSbSa = aSbS bSa <- aSbS SbSa (мы, конечно, можем выбрать S -> e в этом последнем обосновании обратного шага).