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

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

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

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

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

$\displaystyle A_n$→$\displaystyle a_n Ta_n$ | $\displaystyle 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 → $\displaystyle 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