Question

Which of the following problems is undecidable ?
1. To determine if two finite automata are equivalent
2. Membership problem for context free grammar
3. Finiteness problem for finite automata
4. Ambiguity problem for context free grammar

Answer 1

Correct Answer - Option 4 : Ambiguity problem for context free grammar

The correct answer is option 4:

EXPLANATION

Option 1: Decidable

Minimize both finite automata if both are the same having automata then both are equivalent and hence to determine if two finite automata are equivalent is decidable 

Option 2: Decidable

For the context-free language, we have a CYK algorithm for membership problem, so it is decidable

Option 3: Decidable

There is an algorithm for the finiteness problem

ALGORITHM:

Step1: delete states which are not reachable from the initial state and corresponding transitions.

Step 2: delete states and corresponding transitions which are not reachable to the final state.

Step 3: In remaining finite automata, if we find at least one loop and one final state then it is accepting infinite language.

so the finiteness problem is decidable

Option 4: Undecidable

Decidable there is no algorithm for finding ambiguity in grammar, so ambiguity is undecidable.