Give a CFG for L = { x#y : x,y in {0,1}* |x| ≠ |y| }

[shivajikobardan]

I haven't understood this at all. Can you please guide me how we reached to this answer. I want to improve my problem solving here. I don't want to memorize this.

 

[blamocur]

I find it difficult to understand too. Does CFG stand for Context-Free Grammar? Do you need to define a grammar for all all strings 'x#y' where 'x' and 'y' are strings of 0's and 1's whose lengths are different? This is the way it looks to me, but I am not sure -- please explain.

 

[shivajikobardan]

https://www.andrew.cmu.edu/user/ko/pdfs/lecture-11.pdf here is more detail.. you can check it out. But yes, CFG=context free grammar. Exactly we need cfg for grammar for x#y where x,y are different. That is it. You are correct 100%.

 

[blamocur]

View attachment 29700

I haven't understood this at all. Can you please guide me how we reached to this answer. I want to improve my problem solving here. I don't want to memorize this.

I am somewhat rusty on CFGs myself, so take this with a grain of salt:

1. First you define term A which describes strings 'x#y' where 'x' and 'y' are the same length (|x| = |y|)
2. Then you define terms L and R which have longer, or at least not shorter, strings respectively on the left or on the right of '#'.
3. Your final/top term S adds one character either on the left of L or on the right of R to make sure that 'x' and 'y' have different lengths.

Note: I don't know why the top two lines are not combined as 'S -> BL | RB', which would also look right to me.