Which of the functions can a turing machine not perform?
A.
Copying a string
B.
Deleting a symbol
C.
Accepting a pal
D.
Inserting a symbol
Explanation :Different turing machines exist for operations like copying a string, deleting a symbol, inserting a symbol and accepting palindromes.
2.
If T1 and T2 are two turing machines. The composite can be represented using the expression:
A.
T1T2
B.
T1 U T2
C.
T1 X T2
D.
None of the mentioned
Explanation :If T1 and T2 are TMs, with disjoint sets of non halting states and transition function d1 and d2, respectively, we write T1T2 to denote this composite TM.
3.
The following turing machine acts like:
A.
Copies a string
B.
Delete a symbol
C.
Insert a symbol
D.
None of the mentioned
Explanation :A turing machine does the deletion by changing the tape contents from yaz to yz, where y belongs to (S U {#})*.
4.
Which of the functions can a turing machine not perform?
A.
Copying a string
B.
Deleting a symbol
C.
Accepting a pal
D.
Inserting a symbol
Explanation :Different turing machines exist for operations like copying a string, deleting a symbol, inserting a symbol and accepting palindromes.
5.
If T1 and T2 are two turing machines. The composite can be represented using the expression:
A.
T1T2
B.
T1 U T2
C.
T1 U T2
D.
None of the mentioned
Explanation :If T1 and T2 are TMs, with disjoint sets of non halting states and transition function d1 and d2, respectively, we write T1T2 to denote this composite TM.
6.
The machine accept the string by entering into hA or it can:
A.
explicitly reject x by entering into hR
B.
enter into an infinte loop
C.
explicitly reject x by entering into hR and enter into an infinte loop
D.
None of the mentioned
Explanation :Three things can occur when a string is tested over a turing machine:
a) enter into accept halting state
b) enter into reject halting state
c) goes into loop forever
7.
Construct a turing machine which accepts a string with ‘aba’ as its substring.
A.
B.
C.
D.
Explanation :The language consist of strings with a substring ‘aba’ as fixed at its end and the left part can be anything including epsilon. Thus the turing machine uses five states to express the language excluding the rejection halting state which if allowed can modify the graph as:
_1629374069.png)
_1629374129.png)
_1629374171.png)
_1629374216.png)