Constructing context-free grammar

50 Views Asked by At

Construct a context-free grammar generating:

$$\{w\# wR \# | w \text{ is a string of one or more 0s and 1s, and a } \# \text{ is between w and its reverse, and a } \# \text{ is at the end}\}$$

The alphabet of the language is $\{ 0, 1, \# \}$

I came up with this:

S $\to$ 0#0# | 1#1# | 0T0#0T0# | 1T1#1T1#

T $\to$ 0T0 | 1T1 | $\varepsilon$

However, this doesn't work and I think I know why

1

There are 1 best solutions below

0
On

It looks like your strings are limited to palindromes before the # symbols. Let's modify $T$ to be $$T\to 0\# 0\text{ }|\text{ }1\#1\text{ }|\text{ }0T0\text{ }|\text{ }1T1$$

Then we just need $S$ to be $$S\to T\#$$