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.