# Thread: Finding a CFG that generates the following language

1. ## Finding a CFG that generates the following language

I am trying to find a CFG that generates the following language : $\overline{\{ ww^R \mid w \in \Sigma^*\}}$.

I am not sure how to approach this. Can someone help.

2. Say there are only 2 letters; a and b. Then we would have

S → T
T → aTa | bTb | aNb | bNa | a | b
N → aNb | bNa | aNa | bNb | a | b | $\epsilon$

Can you generalize for all alphabets ?

3. I was hoping you didn't give me the answer. Its my fault. I should have said it explicitly. Now its hard for me not to look. I was doing something like so :

Let Σ={a1,a2,…,an}, then the following CFG accepts S.

Q→A1 | B2
A1 → a1 A1 a1 | a2 A1 a2 |…| an A1 an | ϵ | A2
A2 → something goes here and possibly more

Now lets see If I understand. T is forced to make any string of the form $ww^r$ to end with something different then what it starts out with.
And N's purpose is just to enable different types of strings? So in general it would be something like so:

Let Σ={a1,a2,…,an}, then the following CFG accepts S.

S → T
T → a1Ta2 | ... | anTan | U | V
U → a1 | ... | an
V → aiXaj ; where i != j
X → ϵ | U | aiXaj ; where 0 < i,j <= n

Is that sufficient? I tried to separate the steps to make it easier to read and write.

4. Small typo, you meant T → a1Ta1.

The rest is fine.

5. So this is what I came up with. I've been known to make typos. Can you check it :

The set S5 =compliment of { $ww^R |w \in \Sigma^*$} is context–free. We construct a CFG to prove this proposition.
Let Σ={ $a_1,a_2,…,a_n$}, and let 0<i,j≤|Σ| then the following CFG accepts S5.
Q→ $T$
T→ $a_i Ta_j | U | V ; i=j$
U→ $a_i$
V→ $a_i Va_j | U |\epsilon$

6. No this is wrong. For example, T → a1Ta1 → a1Va1 → a1ea1 → a1a1 is valid here ( e stands for epsilon ).

The set S5 =compliment of { $ww^R |w \in \Sigma^*$} is context–free. We construct a CFG to prove this proposition.
Let Σ={ $a_1,a_2,…,a_n$}, and let 0<i,j,k,l≤|Σ| then the following CFG accepts S5.
Q→ $T$
T→ $a_i Ta_j | U | a_k V a_l ; i=j$and $k != l$
U→ $a_i$
V→ $a_i Va_j | U |\epsilon$

the only new thing added was k and l, and $a_k$and $a_l$

8. Seems alright to me

9. Thanks a lot. You guys are really so much help.