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?