Question

Let $\mathit{E}\mathbf{=}\{M|M$ is a DFA that accepts some string with more 1s than 0s}. Show that E is decidable. (Hint: Theorems about CFLs are helpful here.)

Short answer

E is decidable

Step-by-step solution

Definition of DFA

DFA is short for Deterministic finite automata. Automata consists of various states and edges between states to represent the transitions from one state to another. In deterministic finite automata, there is only path from current to next state for some specific input.

Show that E is decidable

Let A = x is a language in which x has more 1s than 0s. There exists a PDA to recognize language A. So, A is a context-free language. Now, build the TM M as follows to determine E:

Construct Bwhich is an intersection of Aand L. The language Bis also context free because Lis regular andAis context free. The language is accepted if Bis empty. Otherwise, it is rejected.

Hence, E is decidable.