The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+13 votes
1.2k views

Which of the following problems is undecidable?

  1. Membership problem for CFGs
  2. Ambiguity problem for CFGs
  3. Finiteness problem for FSAs
  4. Equivalence problem for FSAs
asked in Theory of Computation by Veteran (59.7k points) | 1.2k views

2 Answers

+21 votes
Best answer
  • Membership problem is decidable as it can be solved by parsers.
  • Finiteness problem is decidable for FSAs (also for CFGs), as we just need to check for a loop in the DFA.
  • Equivalence problem for FSAs is decidable as we can take the complement of one FSA (complement of FSA is another FSA), and do an intersection with the other (FSAs are closed under intersection also), giving a new FSA. If this new FSA accept no string, then the given FSAs are equivalent, else not equivalent. 
  • Only ambiguity problem for CFGs are undecidable.

http://gatecse.in/wiki/Grammar:_Decidable_and_Undecidable_Problems

answered by Veteran (367k points)
edited by
+8 votes

equivalence of Regular languages is decidable.

1.Membership,

2.Emptiness,

3.Finiteness,

4.Equivalence,

5.Ambiguity,

6.Regularity,

7.Everything,

8.Disjointedness...

All are decidable for Regular languages.

First 3 for CFL.

Only 1st for CSL and REC.

None for RE.

So option B will be correct one.

answered by Active (2k points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

43,942 questions
49,498 answers
162,339 comments
65,748 users