Question 159: Given a binary alphabet {0,1}, how many different strings are possible of length n, which start with ‘0’ and end with ‘1’?
Options:
Solution: The correct answer is first one. As first and last place is already fixed, there are n-2 places where 0 or 1 can appear. Hence, 2^(n-2) different strings are possible.
Question 145: Suppose one transition of Turing machine
for some integers i, j, k, l and m is encoded in binary form as 0i 1 0j 1 0k 1 0l 1 0m. Here, X1 denotes 0, X2 denotes 1 for binary alphabet. Regarding direction, D1 = L and D2 = R. And, the code for entire TM M consists of all of the codes for the transitions C1, C2, … , Cn in some order separated by pairs of 1’s:
C1 1 1 C2 1 1 . . . . Cn-1 1 1 Cn
What will be the encoding of the following Turing machine as per above technique:
Options:
Solution: The correct answer is option 2. The first transition is “0100100010100”, second transition is “0001010100100”, third transition is “00010010010100” and fourth is “0001000100010010”. They are all separated by “11”.
Question #28: Over a binary alphabet, the language of binary numbers whose value is a prime will have following characteristic:
Options:
A) No string in the set will end with a ‘0’.
B) No string in the set will end with a ‘1’.
C) All strings will end with a ‘1’ apart from one string.
D) All strings will end with a ‘0’ apart from one string.
Solution: The correct answer is C. Only one string ‘10’ (decimal equivalent 2) ends with ‘0’, rest all won’t end with ‘0’ because otherwise they will be multiple of 2.
Bytes of the day 