2

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?

Clev3r
  • 1,568
  • 1
  • 15
  • 28

1 Answers1

2

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

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.

Community
  • 1
  • 1
Grijesh Chauhan
  • 57,103
  • 20
  • 141
  • 208
  • Umm, `wxw^r` - where `w^r` is the reverse of `w` - is not regular. You can prove this easily using the Myhill-Nerode theorem or the pumping lemma for regular languages. – Patrick87 Feb 22 '13 at 16:33
  • Oh wait a sec, you're right. :) Forgot about this one. Looking at the linked question, it looks like I got the right answer there. Oops. – Patrick87 Feb 22 '13 at 16:39