1. ## Is this grammar proof correct, check please?

Prove that the following languages are context-free by giving grammars that accept them
$\{ ww^R \mid w \in \Sigma^*\}$

I am not sure if this valid, but this is my proof :

The set $S = \{ ww^R \mid w \in \Sigma^*\}$} is context –free. We construct a CFG to prove this proposition.
Let Σ={ ${a_1,a_2,$…, $a_n}$}, then the following CFG accepts S.

S→ $A_1$ | $A_2$ |…| $A_n$ | ϵ
$A_1$ $a_1 Ta_1$ | $a_1 a_1$
$A_2$ $a_1 Ta_2$ | $a_2 a_2$

$A_n$ $a_n Ta_n$ | $a_n a_n$

2. What happens to the T ?

3. Sorry, the "S->" should be "T->"

4. In general, we keep the starting symbol separate from all other symbols. Your grammar is alright, but it could have been much shorter.

5. what do you mean? I guess I could add an extra level of indirection. Does the above grammar accept the set S? Can you show some ways then to improve my grammar please?

6. S→ T
T → $a_1Ta_1 | a_2Ta_2 | .... | a_nTa_n | \epsilon$

7. oh i see, thanks

8. Hey, so there is another problem where I have to show that the complement of the above set, is also recognized by some CFG. I am kind of stuck trying to come up with some proof. Can you provide some hints or some idea on how to go about this construction. Thanks