Turing-machines
Question 1 |
(a) Show that Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class or regular languages.
(b) Let L be the language of all binary strings in which the third symbol from the right is a1. Give a non-deterministic finite automaton that recognizes L. How many states does the minimized equivalent deterministic finite automaton have? Justify your answer briefly?
Theory Explanation. |
Question 2 |
Which of the following is/are undecidable?
Given two Turing machines M1 and M2, decide if L(M1)=L(M2). | |
Given a Turing machine M, decide if L(M) is regular. | |
Given a Turing machine M, decide if M accepts all strings. | |
Given a Turing machine M, decide if M takes more than 1073 steps on every string. |
Question 2 Explanation:
Equality problem of recursively enumerable languages is undecidable, so whether two Turing machines accept the same language is undecidable.
Checking whether a Turing machine accepts a regular language is also undecidable.
Completeness problem for recursively enumerable language is undecidable thus whether a Turing Machine accepts all strings is undecidable.
Whether a Turing machine takes more than 1073 steps is decidable as we need to run the Turing Machine only for 1073 steps so no chance of going into an infinite loop hence it is decidable.
Checking whether a Turing machine accepts a regular language is also undecidable.
Completeness problem for recursively enumerable language is undecidable thus whether a Turing Machine accepts all strings is undecidable.
Whether a Turing machine takes more than 1073 steps is decidable as we need to run the Turing Machine only for 1073 steps so no chance of going into an infinite loop hence it is decidable.
Question 3 |
A is recursive if both A and its complement are accepted by Turing machines.
True | |
False |
Question 3 Explanation:
If A is decidable, then A and A' are accepted by Turing machine.
Question 4 |
If there is a Turing machine that enumerates L in canonical order, L is:
ambiguous | |
right – recursive | |
left – recursive | |
recursive |
Question 4 Explanation:
A language L is recursive iff there exists a TM that enumerates L in canonical order.
Question 5 |
Turing machine is more powerful than FMs because
Tape movement is confined to one direction | |
It has no finite state | |
It has the capability to remember arbitrarily long sequences of input symbols | |
None of these
|
Question 5 Explanation:
Turing machines is more powerful than finite machines because it has the capability to remember arbitrarily long sequences of input symbols.
There are 5 questions to complete.