part b question 2: does L={x#y|x!=y and x,y strings from {1,0}*} is Context Free Language?

Hi Ori,

I believe that the grammar stated in the solution published in the site is incorrect (for the HW question).

For instance, we can use it to generate the word: 000111 which shouldn't be in the language.

We tried to think on a grammar for this question:

S-> X# | #Y | X#Y | Y#X

X-> 0X0 | 0X1 | 1X0 | 1X1 | 0

Y-> 0Y0 | 0Y1 | 1Y0 | 1Y1 | 1

But it doesn't hold for all the "small" cases (such as 00#01)

Can you please tell us what is the correct grammar ?

Maybe something like this?

S —> A | C | D

A —> 0B# | 1B# | #0B | #1B

B —> 0B | 1B | epsilon

C —> xCy | A x,y belong to {0,1}

D —> xDy | E

E —> FHI | IHF

F —> 0

I —> 1

H —> xHy | #

A and B handle all cases where one side is empty. C handles the case that the two strings are of different length.

D,E,F,I,H handle all cases which the two strings have the same length, but force a different symbol somewhere. (It's an ambiguous CFL)