5,600 views
25 votes
25 votes

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

2 Answers

Best answer
37 votes
37 votes
  • 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

Correct Answer: $B$

edited by
13 votes
13 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.

Answer:

Related questions

27 votes
27 votes
3 answers
1
go_editor asked Apr 23, 2016
8,416 views
Consider the following Finite State Automaton:The minimum state automaton equivalent to the above FSA has the following number of states:$1$$2$$3$$4$
43 votes
43 votes
6 answers
2
Kathleen asked Sep 21, 2014
13,288 views
Consider the following Finite State Automaton:The language accepted by this automaton is given by the regular expression$b^*ab^*ab^*ab^*$$(a + b)^*$$b^*a(a+b)^*$$b^*ab^*a...
39 votes
39 votes
2 answers
3
Kathleen asked Sep 21, 2014
14,056 views
Which of the following languages is regular?$\left\{ww^R \mid w \in \{0, 1\}^+\right\}$$\left\{ww^Rx \mid x,w \in \{0, 1\}^+\right\}$$\left\{wxw^R \mid x, w \in \{0, 1\}...
26 votes
26 votes
4 answers
4
Kathleen asked Sep 21, 2014
8,321 views
The language $L=\left\{0^i21^i \mid i \geq 0\right\}$ over the alphabet $\left\{0, 1, 2\right\}$ is:not recursiveis recursive and is a deterministic CFLis a regular langu...