Turing Machine & Halting - Free MCQ Practice Test with solutions, GATE

The given diagram is a transition graph for a turing machine which accepts the language with the regular expression {a,b}*{aba}.

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:

The finite automaton for the language {a,b}*{aba}{a,b}* can be constructed using the following steps:

• Start with an initial state.
• Recognise the sequence 'aba' by creating states for each letter.
• Use a final state after recognising the sequence 'aba'.

The total number of states required is 4:

• One initial state.
• Three additional states for each letter in 'aba'.

The finite automata can be represented as:

Thus option a) is correct,

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

D represents the direction in which automata moves forward as per the queue which surely cannot be a starting variable.

A language generating strings which are palindrome is not regular, thus cannot b represented using a finite automaton.

Different turing machines exist for operations like copying a string, deleting a symbol, inserting a symbol and accepting palindromes.

 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.

A turing machine does the deletion by changing the tape contents from yaz to yz, where y belongs to (S U {#})*.

The composite TM accepts the language of palindromes over {a, b} by comparing the input string to its reverse and accepting if and only if the two are equal.