Explore topic-wise InterviewSolutions in .

The CORRECT choice is (d) None of the mentioned

The best explanation: In AUTOMATA THEORY, an o- machine or oracle machine is a abstract machine used to study decision problems. The problem the oracle solves can be of any complexity class. EVEN UNDECIDABLE problems like halting problems can be used.

The correct option is (d) all of the mentioned

Explanation: A n abstract machine ALSO known as abstract computer, is a THEORETICAL model of computer or HARDWARE system in automata THEORY. Abstraction in computing process usually assumes a discrete time paradigm.

The correct answer is (d) NONE of the mentioned

To explain I would SAY: In automata theory, a formal language is called recursively ennumerable language or partially decidable or SEMI decidable or turing acceptable or turing recognizable if there exists a turing MACHINE which will ennumerate all VALID strings of the language.

Correct answer is (a) true

The EXPLANATION: A TM with a semi-infinite tape MEANS that there are no CELLS to the LEFT of the initial head position. A TM with a semi infinite tape simulates a TM with an infinite tape by using a two-track tape.

Correct answer is (d) All of the mentioned

To EXPLAIN: A move of a turing machine is the function of the STATE of finite control and the TAPE SYMBOL just SCANNED.

Right ANSWER is (a) 4

The BEST I can explain: The finite AUTOMATA can be represented as:

The correct answer is (B) halts

The explanation is: If we reach hA or hR, we say TM halts. Once it has halted, it cannot move further, sinced is not defined at any PAIR (hA,X) or (hR,X) where hA = accept halting STATE and hR = reject halting state.

Right answer is (b) {a,b}*{ABA}

The explanation: The given diagram is a TRANSITION GRAPH for a turing machine which accepts the language with the regular EXPRESSION {a,b}*{aba}.

Correct choice is (b) true

The BEST explanation: MULTITAPE TURING machines do have multiple tapes but they they are accessed by separate HEADS.

The correct option is (B) No

The best EXPLANATION: One needs a finite NUMBER of tapes. The proofs that show the equivalence between multi-tape TM and one-band TM rely on the FACT that the number of tapes is BOUNDED.

The correct choice is (a) Statement: An ennumerator is a turing MACHINE mwith extra output TAPE T, where symbols, once written, are never changed.

To EXPLAIN: To ennumerate a SET means to list the elements once at a time, and to say that a set is ennumerable should PERHAPS mean that there exists an algorithm for ennumerating it.

Right choice is (a) an output printer

The best explanation: Here, the turing machine can use the printer as an output device to print STRINGS.

Note: There is no input to an ENUMERATOR. If it doesn’t HALT, it may print an INFINITE set of strings.

Correct option is (a) State true or FALSE:

To explain I would say: INORDER to describe formally what a Turing MACHINE does, we need to develop a notation for configurations or Instantaneous DESCRIPTIONS(ID).

Right option is (d) None of the mentioned

Explanation: Invention of turing MACHINE answered a LOT of questions which included PROBLEMS like decision problem, etc.) . Alan was able to prove the properties of COMPUTATION using such model.

Right option is (a) Multi-tape TURING MACHINE

For explanation I WOULD say: A multitape turing machine is an ordinary turing machine with MULTIPLE tapes. Each tape has its own head to control the read and WRITE.

Correct choice is (a) Statement: We can use the finite control of turing MACHINE to HOLD a finite amount of data.

Explanation: The finite control not only CONTAINS state q but also three data, A, B, C. The following technique requires no EXTENSION to the Turing Machine model. Shaping states this way allows to describe transitions in more systematic way and often to simplify the strategy of the program.

The correct answer is (b) 2^96

Easy EXPLANATION: ACCORDING to the statistics of the question, we will have a FINITE machine with 2^96 STATES.

Right answer is (c) no way

To elaborate: A TWO way infinite tape TURING machine is a turing machine with its input tape INFINTE in both DIRECTIONS, the other component being the sameas the basic MODEL.

Right option is (a) Statement: Turing Machine can CHANGE symbols on its TAPE, whereas the FA cannot change symbols on tape.

Best explanation: The following mentioned is the difference between 2-way FA and TM. Another instance is that TM has a read/write tape head while FA doesn’t.

The CORRECT choice is (c) Both (a) and (b)

To explain I would say: If T is a TURING machine recognizing L, we can MAKE it recognize L’ by interchanging the two outputs. And EVERY recursive language is recursively ennumerable.

The correct option is (d) None of the mentioned

The explanation is: A TURING machine can have many applications like : Enumerator (A turing machine with an OUTPUT printer), FUNCTION COMPUTER, etc.

The correct option is (a) one

The explanation: In a n-track TURING MACHINE, one head reads and writes on all tracks simultaneously. A tape position in a n-track Turing Machine contains n SYMBOLS from the tape ALPHABET.

The correct answer is (a) JFLAP

To EXPLAIN I would SAY: JFLAP is educational software WRITTEN in JAVA to experiment with the topics in automata theory and area of formal LANGUAGES.

Right answer is (C) quadratically

For explanation: Thus, multitape turing MACHINES cannot calculate any more FUNCTIONS than single tape machines.