Полиномиальный размер 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 (пустое слово).

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