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

[shivajikobardan]

Homework Statement

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

Relevant Equations

None

Is my this solution approach correct? I am thinking of making cfg for L1 U L2 U L3 U L4

Where L1=0^m 1^n ----------->m>n

L2=L1 for m<n

L3=1^m 0^n ---->m>n
L4=L3 for m<n

Is my approach correct? If I can do it like that then this will be easy problem for me as well.

 

[lewando]

You are free to decompose a language specification into simpler specifications that can be unionized provided that you get the same specification. Your breakdown does not address the '#' terminal. I also don't see where you are getting 0^m1ⁿ or 1^m0ⁿ constructs from the original specification.