CFG and its reverse

Question

I'm trying to wrap my head around CGS's. Let E^* be 'epsilon star', e be the empty string, and ww^r be w next to the reverse of w.

I know that building up a CFG to accept E^* is a simple S -> 0S | 1S | e.

A CGG that accepts {ww^r} such that w in E^* is a simple S –> 0S0 | 1S1 | e.

Does that mean a CFG accepting {wxw^r} such that w, x in E^* is a sort of 'composition' of these two resulting in S –> 0S0 | 1S1 | e | B where B –> 0B | 1B | e?

Answer 1

Yes, your grammar is correct!

CFG to {wxw^r} such that w, x in E^* is S –> 0S0 | 1S1 | e | B where B –> 0B | 1B | e is correct grammar.

But important is Language {wxw^r} such that w, x in E^* is Regular Language so it also possible to write Left-Linear and Right-Linear Grammars.

A Right-Liner equivalent Grammar for this language is:

S --> 0B | 1A | ^
B --> 0B | 1B | 0
A --> 0A | 1A | 1

And Left Liner equivalent is:

S --> B0 | A1 | ^
B --> B0 | B1 | 0
A --> A0 | A1 | 1

Its regular expression is:

0(0 + 1)*0 + 1(0 + 1)*1 + ^

A similar language I described here in my answer with DFA.

note: language structure is same but symbol are not, also there is ^ null string is not possible. Also there is + on ( 0 + 1) here is *

Its DFA

Additionally, I would also encourage you to view DFA for 0(1 + 0)*0 + 1(1 + 0)*1 . Notice a small change of ^ in RE but DFAs are quite different.