HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

Is every regular language Turing-decidable, and how can we prove this?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thiscanregulareveryandlanguagedecidableprovehowturing

Problem

I know every regular language is Turing-acceptable, but does that imply it is Turing-decidable?

Solution

Every regular language is Turing-decidable and therefore Turing acceptable / recognisable (but note that Turing acceptable does not imply Turing decidable).

Suppose you are given a DFA D such that L = L(D). One can construct a Turing Machine T that simulates D. T's states will be similar to D's. On reaching the end of the input, if T is in a state that corresponds to a final state of D, T halts and accepts; otherwise it halts and rejects.

Context

StackExchange Computer Science Q#10971, answer score: 7

Revisions (0)

No revisions yet.