McqMate

Q. |
## Which of the following problems is undecidable? |

A. | Membership problem for CFGs |

B. | Ambiguity problem for CFGs |

C. | Finiteness problem for Finite state automata FSAs |

D. | Equivalence problem for FSAs |

Answer» B. Ambiguity problem for CFGs |

3.8k

0

Do you find this helpful?

58

View all MCQs in

Theory of ComputationNo comments yet

- Which of the following problems is undecidable?
- Out of the three decision problems P1, P2 and P3, P1 is decidable and P2 is undecidable. The statement that holds true is
- Which of the following problem is undecidable?
- Let S be an NP-complete problem, Q and R be two other problems not known to be in NP. Q is polynomial-time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?
- Consider three problems P1, P2 and P3. It is known that P1 has polynomial time solution and P2 is NP-complete and P3 is in NP. Which one of the following is true.
- 3-SAT and 2-SAT problems are
- Which of the following strings is not generated by the following grammar? S → SaSbS ε
- Consider the following problem x. Given a Turing machine M over the input alphabet Σ, any state q of M. And a word w Є Σ*, does the computation of M on w visit the state q? Which of the following statements about x is correct?
- Consider the following CFG S → aB S → bA**spaceB → b A → a**spaceB → bS A → aS**spaceB → aBB A → bAA**space Consider the following derivation **spaceS ⇒aB**space⇒aaBB**space⇒aaBb**space⇒aabSb**space⇒aabbAb**space⇒aabbab**space This derivation is
- 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)