1

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.

John Takiyama
  • 21
  • Yes, it’s fine. – Brian M. Scott May 23 '13 at 23:24
  • I agree, looks fine to me. – kgraney May 24 '13 at 00:12
  • 1
    Wait a minute! How can $x# y$ be in ${0,1}^$? It contains a symbol $#$ that is neither $0$ nor $1$. Was the intention rather that $x$ and $y$ should be in ${0,1}^$? If so, then your grammar is OK. If the definition of $L$ is taken literally, then $L$ is empty and an even simpler grammar works. – Andreas Blass May 24 '13 at 21:32
  • in definition of this language, must be written L={X#Y|X,Y $\in$ {0,1}* & |x|=|y|} – a d May 31 '13 at 13:45

1 Answers1

0

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

a d
  • 274