Полиномиальный размер CFG такой, что каждый терминал в слове встречается четное число раз (большой алфавит)

Question

Найти контекстную грамматику (CFG) для языка L всех такие слова, что каждый терминал в слове встречается четное число раз по возможно большому алфавиту Σ

Мой длинный подход (единственный нетерминал - S):

S ⟶ ε | SS

x ∈ Σ: S ⟶ xSx

x, y ∈ Σ: S ⟶ xxSyy | yySxx | xySxy | xySyx | yxSyx | yxSyx

Это правильно? Продукция производит правильные слова, они генерируют все слова?

РЕДАКТИРОВАТЬ: Может ли CFG на большом алфавите описывать язык, где каждый терминал появляется четное число раз?

EDIT_2: Если решение существует, возможно ли, чтобы нормальная форма Хомского была полиномом от | Σ |

Answer 1

Существует даже обычная грамматика для достижения этой цели. Поскольку каждая обычная грамматика по определению не зависит от контекста, ответ - «да». Также возможно построить конечный автомат, но так как вы попросили грамматику ...

Вот как: вспомните, что обычная грамматика допускает правила вида A -> b C или A -> b или A -> epsilon, где A и C не являются терминалами, а b является терминалом. Это по существу означает, что каждый нетерминал генерирует терминал и другой нетерминал, который будет генерировать остальную часть строки; Можно сказать, что каждый нетерминал кодирует определенное свойство в строках, которые он генерирует.

Рассмотрим теперь все подмножества алфавита сигма. Поскольку предполагается, что Sigma конечна, то есть и набор подмножеств (powerset). Пусть набор нетерминалов будет блоком питания Sigma.

Начните с правила: {} -> a {a} для каждого терминала a. Для каждого нетерминала X добавьте правило X -> a X- {a}, если a находится в X; или X -> a X + {a}, если a не находится в X (Я небрежно пишу + и - для объединения и разности здесь).

Наконец, добавьте {} -> epsilon (пустое слово).

Грамматика кодирует в своих нетерминалах именно те наборы терминалов, которые появились в нечетном числе и, следовательно, должны быть снова "отменены".