Applied Course | Mock GATE | Test 1 | Question: 53

Question

Which of the following languages are Decidable?

1. $\text{INFINITE}_{\text{DFA}} = \{ \langle A \rangle \mid \text{ A is DFA and L(A) is an Infinite Language} \}$
2. $\text{INFINITE}_{\text{PDA}} = \{ \langle A \rangle \mid \text{ A is PDA and L(A) is an Infinite Language} \}$
3. $\text{INFINITE}_{\text{TM}} = \{ \langle M \rangle \mid \text{ M accepts String of Length} \geq 2018 \}$
4. $\text{AMBIG}_{\text{CFG}} = \{ \langle G \rangle \mid \text{ G is an Ambiguous CFG} \}$

 

• A. I and II only
• B. II and III only
• C. III and IV only
• D. II and IV only

Answer 1

I. $\text{INFINITE}_{\text{DFA}}$
Membership Problem of regular languages are Decidable.
Consider the following Language $L=\{ \epsilon, a, b, ab, aa, ba, bb, \dots \}$

II. $\text{INFINITE}_{\text{PDA}}$ Membership Problem of context free languages are Decidable. CYK Algorithm is used to prove that the given string is a valid member of the language or not.
III. $\text{INFINITE}_{\text{TM}} = \{ <M> \mid \text{ M accepts String of Length} \geq 2018 \}$
Membership problem of TM is Undecidable
IV. I. $\text{AMBIG}_{\text{CFG}} = \{ <G> \mid \text{ G is an Ambiguous CFG} \}$
Ambiguity of CFG is Undecidable
I and II only.