Question

Let . Show that A is decidable.

Short answer

A is decidable.

Step-by-step solution

Decidable languages

A language is said to be decidable if the inputs of a language are accepted by a Deterministic Finite Automata.

Explanation

A language is decidable if the input string of a language is accepted by a Turing Machine. Consider the Turing machine M that decides the language A

The following TM decides A.

“On input

1. Construct a DFA, Dwhich accepts every string containing an odd number of 1s.
2. Construct a DFA, B such that$L\left(B\right)=L\left(M\right)\cap L\left(D\right).$
3. Test whether $L\left(B\right)=\varphi ,$using the $E_{DFA}$decider T from the Theorem 4.4.
4. If Taccepts, accept; if T rejects, reject.”

Therefore, the language is decidable, and has been proven.