The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+13 votes

Which of the following problems is undecidable?

- Membership problem for CFGs
- Ambiguity problem for CFGs
- Finiteness problem for FSAs
- Equivalence problem for FSAs

+20 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

+6 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 1^{st} for CSL and REC.

None for RE.

So option B will be correct one.

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 4k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 449
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,058 questions

45,554 answers

131,893 comments

48,911 users