If you want to make money online : Register now

[Solved]: how to prove a language is decidable

, , No Comments
Problem Detail: 

Hopefully this is not a duplicate

How do I prove a Language L={a,b,c} is decidable or not

I read somewhere that if a turing machine accepts a language and halts on every input string then the language is decidable.

Having said that how do i design / prove that a turing machine accepts {a b c}

I am new to concepts of automata and compelexity so please don't kill me if this is too basic for a question

Asked By : Swathi

Answered By : Yuval Filmus

By definition, a language is decidable if there exists a Turing machine that accepts it, that is, halts on all inputs, and answers "Yes" on words in the language, "No" on words not in the language. Therefore one way of showing that a language is decidable is by describing a Turing machine that accepts it.

There are many offline and online resources on Turing machines. For example, here are some introductory slides on Turing machines: part 1, part 2.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32246

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback