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?

  • $\begingroup$ I am sorry but I originally published it in StackOverflow where I saw plenty of questions about TMs. Then I was sent here... then now you -1 my question and send me to Computer Science... Nobody agrees. I think my question is strongly related to theoretical computer science, though... $\endgroup$ – Bea Mar 5 '14 at 19:46
  • 2
    $\begingroup$ no dispute that this relates to theoretical computer science. However, it's the "level" of the question that places it in CS.SE. I'm sorry that SO moved you here: they should have moved you straight to CS.SE $\endgroup$ – Suresh Mar 5 '14 at 19:56
  • $\begingroup$ Yes, thanks. I read the help center and I agree the question does not belong here. I did not even know about this site, but this is what I was told in SO... Sorry about that $\endgroup$ – Bea Mar 5 '14 at 19:58
  • $\begingroup$ too many acronyms around ... I have done quite a bit of automata theory, but I do not recall seeing AFDA before. $\endgroup$ – babou Mar 6 '14 at 13:13

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.

  • $\begingroup$ Thanks. 2) So I assume that despite k being defined as k >= 0 it is bound to be a natural number (so finite). 1) I think this is solved the same way too - if the input string is finite, then there is no possible infinite "w" and the automaton will certainly halt, correct? $\endgroup$ – Bea Mar 5 '14 at 19:54

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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy