1
Which of the following problems is undecidable?
EXPLANATION
Formal Languages & Automata
- Decidability in Formal Languages and Automata:
- Decidable Problems:
- Equivalence of two finite automata: Decidable by testing language emptiness of $(L_1 \cap \overline{L_2}) \cup (\overline{L_1} \cap L_2)$.
- Membership for CFG: Decidable via CYK or Earley parsing algorithm ($O(n^3)$).
- Finiteness for FA: Decidable by checking cycles on paths to accepting states.
- Undecidable Problem:
- Ambiguity of Context-Free Grammars: Whether an arbitrary CFG is ambiguous (can generate two distinct parse trees for the same string) is proven to be Undecidable by reduction from Post's Correspondence Problem (PCP).
- Conclusion: Ambiguity problem for context free grammar (Option 4).
Correct option: (4) Ambiguity problem for context free grammar
Explanation not matching this question?
क्या व्याख्या इस प्रश्न से मेल नहीं खा रही?
Report
Want to practice this paper in exam conditions?
क्या आप परीक्षा जैसे माहौल में अभ्यास करना चाहते हैं?
Test yourself in 5-question batch format with timer and hidden answers.
5-प्रश्नों के बैच फॉर्मैट, टाइमर और छिपे उत्तरों के साथ खुद को परखें।
Start Practice Mode →
प्रैक्टिस टेस्ट मोड शुरू करें →