Question

2. (10 points) For a string s (0,1 let s2 denote the number represented by s in the binary numeral system. For example 1110 in binary has a value of 14. Consider the language: meaning it contains all strings u#w such that u + 1 -w holds true in the binary system. For example, 1010#1011 L and 0011 #100 e L . Construct a TM that decides this language. Provide an implementation-level definition of your TM

For a string s ∈ {0, 1} let denote the number represented by in the binary * s2 s numeral system. For example 1110 in binary has a value of 14 . Consider the language: L = {u#w | u,w ∈ {0, 1} , u } , * 2 + 1 = w2 meaning it contains all strings u#w such that u + 1 = w holds true in the binary system. For example, 1010#1011 ∈ L and 0011#100 ∈ L . Construct a TM that decides this language. Provide an implementation-level definition of your TM.

Answer 1

Implementation is simple. Given string u#w, we will add 1 to string u( which can be done by flipping rightmost bit from 0 to 1 if rightmost bit is 0 and if rightmost bit is 1 then flip it to 0 and move left and do this same till 0 is not encountered where we will flip 0 to 1). One this is done, then we do bit wise comparison of string u and w from right to left to check if they are equal. If they are equal then accept else reject.

I am assuming that in string u#w , string w does not contains unnecessary 0s at the left end.

//remove useless 0 by putting blank B from the leftmost end of string u, like if u= 0011, then it will make u = 11.

5(go, 0 (go, B, R)

$\delta(q_0,\#) \rightarrow (q_2,\#,L)$ //This happen if u is empty i.e. 0 and hence we will go to q₂ to add 1 into it

$\delta(q_0,1) \rightarrow (q_1,1,R)$ //Now go to rightmost end of string u

$\delta(q_1,0) \rightarrow (q_1,0,R)$

$\delta(q_1,1) \rightarrow (q_1,1,R)$

$\delta(q_1,\#) \rightarrow (q_2,\#,L)$ //Move one step left to reach end of string u

$\delta(q_2,0) \rightarrow (q_3,1,R)$ //If last bit is 0 then make it 1 and move right

$\delta(q_2,1) \rightarrow (q_2,0,L)$ //else make 1 to 0 till 0 is not encountered

$\delta(q_2,B) \rightarrow (q_3,1,R)$ //If we reach to blank( this happen if u = 11) then replace blank by 1 and move right

Now that reaching at state q₃ means out task of adding 1 to u has been done. Now we will start comparing input u#w which must be equal after 1 has been added into u.

From state q₃ we will move to rightmost end of entire string u#w i.e. at blank position

$\delta(q_3,0) \rightarrow (q_3,0,R)$

$\delta(q_3,1) \rightarrow (q_3,1,R)$

$\delta(q_3,\#) \rightarrow (q_3,\#,R)$

$\delta(q_{3},X) \rightarrow (q_{3},X,R)$ //X is also a symbol

$\delta(q_3,B) \rightarrow (q_4,B,L)$ //If q₃ reaches blank then move leftward

$\delta(q_4,X) \rightarrow (q_4,X,L)$ //X is special symbol which we clarify

$\delta(q_4,0) \rightarrow (q_{50},X,L)$ //If leftmost end contains 0 then turn it to X and go to state q₅₀

//If leftmost end contains 1 then turn it to X and go to state q₅₁

')(ga. 1) → (951, Xi L)

$\delta(q_{50},1) \rightarrow (q_{51},1,L)$ //simply move to left

$\delta(q_{50},0) \rightarrow (q_{50},0,L)$

$\delta(q_{51},0) \rightarrow (q_{51},0,L)$

$\delta(q_{51},1) \rightarrow (q_{51},1,L)$

$\delta(q_{50},\#) \rightarrow (q_{60},\#,L)$ Now string u has came

$\delta(q_{51},\#) \rightarrow (q_{61},\#,L)$

$\delta(q_{60},X) \rightarrow (q_{60},X,L)$

$\delta(q_{61},X) \rightarrow (q_{61},X,L)$

Remember that state is q₆₀ or q₆₁ depends on what was rightmost input in string w that we are matching with in string u

$\delta(q_{60},1) \rightarrow (q_{reject},1,R)$ //This means strings are not matched, then reject string and halt

$\delta(q_{61},0) \rightarrow (q_{reject},0,R)$ //This means strings are not matched, then reject string and halt

//This means string are matched till now and go to q₃ to perform matching of remaining string

5G100 . 0) → (gs, X, R)

$\delta(q_{61},1) \rightarrow (q_{3},X,R)$ // Strings are matched till now

$\delta(q_{4},\#) \rightarrow (q_{7},\#,L)$ //This means entire string w is matched, now we just need to see if entire string in u is also matched or not

$\delta(q_{7},X) \rightarrow (q_{7},X,L)$ //Simply move left

$\delta(q_{7},0) \rightarrow (q_{reject},0,L)$ //this means some input is still there in string u and hence not matched, so reject

$\delta(q_{7},1) \rightarrow (q_{reject},1,L)$

$\delta(q_{7},B) \rightarrow (q_{accept},B,L)$ //If q₇ reached blank then entire string is matched and hence accept

Please comment for any clarification.