Context Free Grammar Equal Lengths

Question

Consider the language L = {x#y is in {0,1}* where |x| = |y|}

Would this CFG be a sufficient definition of the language L?

S->0S0 | 0S1 | 1S0 | 1S1 | #

Thanks.

Answer 1

No, from Definition of this language, we can generate '#0#1#' and in your grammar, we cant generate this.

First way: Change definition of language to:

$$L=\{X\#Y \mid X,Y\in\{0,1\}^* \& |X|=|Y| \}$$

Second way: Change grammar

$$S\rightarrow0S0|1S1|0S1|1S0|0S\#|\#S0|1S\#|\#S1$$

Of course i think your goal is First Way