Understanding decidability

Question

Sorry this is a basic question to understand decidability. It is the first time I see it in my undergrad course.

1) I am reading why the language AFDA is decidable and why ATM (halting problem) is not. The explanation says that the emulated TM in ATM might loop forever. I agree, because a specific input string might make the TM going forever, always able to apply rules and never halting.

However, why is AFDA decidable? What if the automaton never reaches any of its final states and keeps looping? There might be a specific input that makes the FDA never reach such states. I understand that once the input string finishes, it will be either accepted or rejected, but what if it does not finish? I'm assuming the input string in the TM can be infinite.

2) The same problem I have here:

A = { 0^k 1^k | k >= 0}

This language is decidable, and it will halt in strings like 10, 010101, etc but what if the input string is infinite 01010101...... it will never end.

What am I missing?

Answer 1

1) The automaton "halts" after it reads the input, whether or not it reaches a final state. It accepts the input if, when it halts, it's in a final state.

2) Inputs are always finite strings. There are generalizations of finite automata ($\omega$-automata of various kinds [Buchi, Rabin, Muller]) that accept $\omega$-words (countably infinite strings) as inputs.

Answer 2

1) I haven’t heard of the “AFDA” acronym before, but I assume you mean the acceptance-problem for Deterministic Finite Automatons. In that case, the answer is that the input strings in this machine model are always finite. Because the DFA always halts, a Turing machine can decide whether a given DFA accepts the input or not.

2) Again, in all common machine models input strings are always finite, especially in undergrad courses where you typically adress finite-state machines, Turing machines, pushdown automata,… (Unless, of course, infinite input strings are explicitly allowed in your specific machine model.)