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

shivajikobardan

Junior Member
Joined
Nov 1, 2021
Messages
79
1636787829254.png

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

Full Member
Joined
Oct 30, 2021
Messages
903
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.
 

blamocur

Full Member
Joined
Oct 30, 2021
Messages
903
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.
 
Top