I spend a lot of time but still can't understand how to solve this. I have the answer. Can you tell me how he come up with it?
Is there a specific rules or standard construct I can follow? I know the rules for union and concatenation but not when it's reversed.
If x
is a (possibly improper) substring of y
, then x^r c y
can be written as x^R c wxz
where w
and z
are arbitrary strings over (a+b)*
.
Now we can try to "slice" the strings in this language to see how they can be generated by CFGs. The non-regular part of this is making sure that x^R
and x
come out right; the rest is trivial. So we need some rules like:
S -> aXa | bYb | c
This gives us x^R c x
. We are missing the w
and the z
. The w
we can add by letting any arbitrary string come after c
:
S -> aSa | bSb | cA
A -> aA | bA | e
The z
we can get by changing S
to T
and adding a new S
that produces T
followed by anything:
S -> TA
T -> aTa | bTb | cA
A -> aA | bA | e
All we neglected to ensure was that |x| > 1
. We do that by changing T -> cA
to two productions T -> acAa | bcAb
. This yields the suggested grammar (Not the only right one, just one grammar that works) and explains how we got there.