Home » Theory of Computation » Theory of computation miscellaneous » Question

Theory of computation miscellaneous

Theory of Computation

  1. Which of the following problems is undecidable?
    1. Membership problem for CFGs
    2. Ambiguity problem for CFGs
    3. Finiteness problem for FSAs
    4. Equivalent problem for FSAs
Correct Option: B

Finite state automata (FSA) has no undecidability CFL membership problem is also decidable. So option (b) i.e Ambiguity of CFL cannot be decidable.



Your comments will be displayed only after manual approval.