- Computer Science Engineering (CSE)
- Theory of Computation
- Unit 1
- Grammars that can be translated to DFAs:

Q. |
## Grammars that can be translated to DFAs: |

A. | Left linear grammar |

B. | Right linear grammar |

C. | Generic grammar |

D. | All of these |

Answer» B. Right linear grammar |

View all MCQs in:
Theory of Computation

- 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)
- The …………. is said to be ambiguous if there exist at least one word of its language that can be generated by the different production tree .
- All NonNull words of the CFL can be generated by the corresponding CFG which is in CNF i.e the grammar in CNF will generate the same language except the:
- What is the highest type number which can be applied to the following grammar? S —>Aa, A —> Ba, B —>abc
- FSM can recognize
- Consider the following statements about the context free grammar G = {S - >SS,S - >ab,S ->ba, S - ε} I. G is ambiguous II. G produces all strings with equal number of a’s and b’s III. G can be accepted by a deterministic PDA. Which combination below expresses all the true statements about G?
- Suppose that a problem A is known to have a polynomial-time verification algorithm. Which of the following statements can be deduced.
- A FSM can be considered, having finite tape length without rewinding capability and unidirectional tape movement
- The symbols that can’t be replaced by anything are called -----------------
- Two persons X and Y have been asked to show that a certain problem p is NP-complete. X shows a polynomial time reduction from the 3-SAT problem to p and Y shows a polynomial time reduction from p to 3-SAT. From these reduction it can be inferred that

Login to Continue

It will take less than 2 minutes

Report MCQ