TOC QUIZ

An instantaneous description of Turing machine consists of:

• Present state and input to be processed

• Present state and entire input to be processed

• Present input only

Why Turing machine is more powerful than Finite automata?

• Turing machine head movement is continued to one direction.

• Turing machine head moment is in both directions

• Turing machine has capability to remember arbitrary long sequence of input string.

A universal Turing machine is a

• Single tape Turing machine

• Two-tape Turing machine

• Reprogrammable Truing machine

The machine accept the string by entering into hA or it can:

• explicitly reject x by entering into hR

• enter into an infinte loop

• explicitly reject x by entering into hR and enter into an infinte loop

Which of the following can accept even palindrome over {a,b}

• Push down Automata

• Turing machine

• NDFA

• All of the mentioned

The format: A->aB refers to which of the following?

• Chomsky Normal Form

• Greibach Normal Form

• Backus Naur Form

Given grammar G:(1)S->AS (2)S->AAS (3)A->SA (4)A->aa Which of the following productions denies the format of Chomsky Normal Form?

• 2,4

• 1,3

• 1, 2, 3, 4

• 2, 3, 4

A PDA machine configuration (q, a, X) can be correctly represented as:

• unprocessed input, stack content, current state)

• (current state, unprocessed input, stack content)

• (current state, stack content, unprocessed input)

The push down automata accepts the input string in form of

• Finial state

• Empty stack

• Both (a) and (b)

PDA consist of:

• State

• Unconsumed input

• Stack content

• All of the mentioned