Question

Show that ${\mathit{A}}_{\mathbf{D}\mathbf{F}\mathbf{A}}\mathbf{\in }\mathit{L}$

Short answer

The space required to run this simulation is $O\left(logn\right)$.

Step-by-step solution

Step-1: DFA

Let$A_{DFA}$be the language

{ $(A,w)$| A is a DFA that accepts W }

where $(A,w)$denotes the encoding of A followed by W.

Step-2: To explain turning machine 

To decide$A_{DFA}$, build a turning machine (TM).

When M takes $(A,w)$, a DFA and a string M as input, it performs A on W by keeping track of $A\text{'}s$ current state and its current head location and updating them as needed.

Because M may be recorded simply placing a pointer into its input, the space required to run this simulation is $O\left(logn\right)$.