I am trying to revise for my exams and going through my lecture slides and recordings, my lecturer didn't really give a clear example of why Regular languages are decidable.

She mentioned that it was because Regular Languages can be represented in Finite Automata, and can be classified as a subset of regular languages. As finite automata are special kinds of Turing Machines with bounded tapes in which you don't write anything, and just gave the definition of what decidable is, which in her words are "a Language L is Turing-decidable if there exists a TM that can decides it".

I sort of what she is getting at, but it seems extremely vague and over generalised that I don't fully understand what she is saying.

  • 3
    $\begingroup$ If you accept that regular languages are decided by finite automata, that a finite automaton is just a special kind of Turing machine and that decidable means that there's a Turing machine that decides it, you're done. Is there one of the steps that you're not comfortable with? $\endgroup$ Apr 7 '17 at 15:54
  • 1
    $\begingroup$ "It is decidable if there is a TM that decides it" is certainly a confusing definition, because it sounds circular. I think it's more clear to say that a language is decidable iff there is a TM, which halts on all inputs, that accepts a string iff it is in the language. $\endgroup$ Apr 7 '17 at 17:13
  • 2
    $\begingroup$ @user34258 That's just unwrapping the formal definition of what "TM decides L" means. $\endgroup$
    – Raphael
    Apr 7 '17 at 19:25
  • $\begingroup$ Have you tried developing a formal proof along the lines your teacher gave you? It's fairly straight-forward. $\endgroup$
    – Raphael
    Apr 7 '17 at 19:26

I will try to explain it without a formal proof,

Imagine a turing machine where you have input written over a tape you can only but read only the input and not modify it. In addition you can only visit the length of the tape where the input is written. This gives you a finite number of configurations to traverse. Thus after a finite number of moves you can $Decide$ whether or not the word word belongs to the input language ; making regular languages decidable.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.