I am trying to find a CFG that generates the following language :$\displaystyle \overline{\{ ww^R \mid w \in \Sigma^*\}}$.
I am not sure how to approach this. Can someone help.
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 $\displaystyle 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.
So this is what I came up with. I've been known to make typos. Can you check it :
The set S5 =compliment of {$\displaystyle ww^R |w \in \Sigma^*$} is context–free. We construct a CFG to prove this proposition.
Let Σ={$\displaystyle a_1,a_2,…,a_n$}, and let 0<i,j≤|Σ| then the following CFG accepts S5.
Q→$\displaystyle T$
T→$\displaystyle a_i Ta_j | U | V ; i=j $
U→$\displaystyle a_i$
V→$\displaystyle a_i Va_j | U |\epsilon$
Oh I see, how about this
The set S5 =compliment of {$\displaystyle ww^R |w \in \Sigma^*$} is context–free. We construct a CFG to prove this proposition.
Let Σ={$\displaystyle a_1,a_2,…,a_n$}, and let 0<i,j,k,l≤|Σ| then the following CFG accepts S5.
Q→$\displaystyle T$
T→$\displaystyle a_i Ta_j | U | a_k V a_l ; i=j $and $\displaystyle k != l $
U→$\displaystyle a_i$
V→$\displaystyle a_i Va_j | U |\epsilon$
the only new thing added was k and l, and $\displaystyle a_k $and $\displaystyle a_l$