Can a CFG over large alphabet describe a language, where each terminal appears even number of times?
If yes, would the Chomsky Normal Form be polynomial in |Σ| ?
EDIT: What about a language where each terminal appears 0 or 2 times?
EDIT: Solving this may give interesting extension to "Restricted read twice BDDs and context free grammars"
Find a context-free grammar (CFG) for the language L of all words such that each terminal in a word occurs even number of times over a possibly large alphabet Σ
My long aproach is (the only nonterminal is S):
S ⟶ ε | SS
x ∈ Σ : S ⟶ xSx
x,y ∈ Σ : S ⟶ xxSyy | yySxx | xySxy | xySyx | yxSyx | yxSxy
Second try, incremental approach.
S ⟶ ε | SS
Terminal productions (suboptimal): x,y ∈ Σ : S ⟶ xx | yy |xxyy | yyxx | xyxy | xyyx | yxyx | yxxy
Incremental: x ∈ Σ : S ⟶ SxSxS
By the way, the homework is over now.
Technically it wasn't a homework assigned to me. I don't know the answer and thought the question was easy. Best.
EDIT: I didn't award the bounty :-)