McqMate

Q. |
## Fred created a new automaton model which is a push down automaton but with two stacks and the added ability of having commands which do not read input tape but which can pop from one stack and push into the other.This new automaton can recognize (choose strongest result) |

A. | Context Free Language |

B. | Context sensitive language |

C. | Regular language |

D. | Languages recognizable by Turing machine |

Answer» D. Languages recognizable by Turing machine |

902

0

Do you find this helpful?

1

View all MCQs in

Theory of ComputationNo comments yet

- Consider a stack, which is limited to 10 items. The language accepted by a push- down automaton in such stack is best described as
- A FSM can be considered, having finite tape length without rewinding capability and unidirectional tape movement
- Which of the following is true with respect to Kleene’s theorem? 1 A regular language is accepted by a finite automaton. 2 Every language is accepted by a finite automaton or a turingmachine.
- Consider the following Finite State Automaton The language accepted by this automaton is given by the regular expression
- Which of the following are decidable? 1) Whether the intersection of two regular language is infinite. 2) Whether a given context free language is regular. 3) Whether two push down automata accept the same language. 4) Whether a given grammar is context free.
- State table of an FSM is given below. There are two states A And B, one input and one output. Let the initial state be A = 0 and B = 0. To take the machine to the state A = 0 and B = 1 with output = 1 the minimum length of input string required will be
- Which of the following assertions about Turing Machines is true? Blank symbol(s) may occur in the input. At any stage of a computation, there are only finitely many non-blank Symbols on the tape.
- The language accepted by a Push down Automata:
- The language accepted by a Push down Automata:
- Match all items in Group 1 with correct options from those given in Group 2. List I List II**spaceP. Regular Expression 1. Syntax analysis**spaceQ. Push down automata 2. Code Generation**spaceR. Dataflow analysis 3. Lexical analysis**spaceS. Register allocation 4. Code optimization