give a context free grammar for the following language over the alphabet {0,1,#}
L = { x#y | x,y ∈ {0,1}* and x ≠ y }
HINT: Under what conditions are the two strings different whose lengths are different? Under what conditions are two strings different whose length are the same ?
I have been working on this problem since the past 3 hours and I still cant figure it out. I would really appreciate it if you can help me out.
But i have come up with this grammar ( I DONT THINK THIS IS CORRECT THOUGH )
<goal> ::= <any01> | <any10> | <uneq00> | <uneq11>
<any01> ::= 0# | #1 | 0<any01> | <any01>1
<any10> ::= 1# | #0 | 1<any01> | <any01>0
<uneq00> ::= <uneq00L> | <uneq00R>
<uneq00L> ::= 0<eq00> | 0<uneq00L>
<uneq00R> ::= <eq00>0 | <eq00R>0
<eq00> = "#" | 0<eq00>0
Please help me out friends.Thanks!
RSS Feed