Thread: Finding a CFG that generates the following language

I am trying to find a CFG that generates the following language : .

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

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 |

Can you generalize for all alphabets ?

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 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.

Small typo, you meant T → a1Ta1.

The rest is fine.

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


The set S5 =compliment of { } is context–free. We construct a CFG to prove this proposition.
Let Σ={ }, and let 0<i,j≤|Σ| then the following CFG accepts S5.
Q→
T→
U→
V→

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

Oh I see, how about this

The set S5 =compliment of { } is context–free. We construct a CFG to prove this proposition.
Let Σ={ }, and let 0<i,j,k,l≤|Σ| then the following CFG accepts S5.
Q→
T→ and
U→
V→

the only new thing added was k and l, and and

Seems alright to me

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