LEXICAL ANALYSIS
REGULAR EXPRESSIONS AND FINITE AUTOMATA
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
A Turing machine prints specific letter.
|
|
|
A Turing machine computes product of two numbers.
|
|
|
An arbitrary Turing machine halts after fifty steps.
|
|
|
None of these
|
Detailed explanation-1: -Another special state is the halt state. The Turing machine’s computation ends when it enters its halt state. It is possible that a computation might never end because the machine never enters the halt state. This is analogous to an infinite loop in a computer program.
Detailed explanation-2: -The halting problem is a decision problem about properties of computer programs on a fixed Turing-complete model of computation, i.e., all programs that can be written in some given programming language that is general enough to be equivalent to a Turing machine.
Detailed explanation-3: -The halting problem on Turing machines is undecidable. Conversely, the halting problem on finite state automata is easily decidable; all finite state automata halt. Thus it’s important to specify the model. The halting problem on usual computers is also decidable.
Detailed explanation-4: -Whether the language generated by a Turing machine is always un-decidable. Therefore, Is L(M) regular is un-decidable.