Consider the problem or determining, from a given PDA. whether the PDA has infin

Question

Consider the problem or determining, from a given PDA. whether the PDA has infinite language or not. is this decidable or not? And why or why not? Decidable because from class we saw that we can detect looping conditions and just delete them if there are any (and say that It is infinite if there are such conditions). Decidable: because of the pumping lemma for CFLs. Undecidable: one would need to keep track of infinitely many strings that are accepted by the PDA (through simulation). Undecidable If one can decide this problem, then one can decide the acceptance problem for TMs, which we already know is undecidable None of the above is correct My friend is curious about the language: L = {M is a TM and accepts at least 3 strings}. Is this language decidable? Why or why not? Decidable: test strings until 3 are found to be accepted by the machine. Decidable: the machine's language must be finite, and therefore decidable. Undecidable we can construct a decider for A_TM assuming a decider for this language Undecidable we can construct a decider for this language assuming a decider for A_TM None of the above is true

Explanation / Answer

Decidable: because of the pumping lemma for CFLs

Un decidable one would need to keep track of infinitely many strings that are accepted by the PDA (through simulation).

Decidable: test strings until 3 are found to be accepted by the machine

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.