2
$\begingroup$

Let $M$ be a Turing machine, $\Sigma$ an alphabet, $t \in \mathbb{N}$

$L = \{ w \in \Sigma^* : w$ is accepted by $M$ by at most $t$ steps$\}$

I want to show that $L$ is regular.

My attempt:

I'm trying to do this directly by constructing a DFA for $L$.

Let $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$

Define $\Gamma_0 = \Gamma \cup \{\sqcap\}$ where $\sqcap \notin \Gamma$.

Set $Q_0 = Q \times \Gamma_0^{t+1} \times \{i\}_{i=1}^{t+1}$ a finite set.

For $q \in Q$, $(a_1,..,a_{t+1}) \in \Gamma^{t+1}$, $1 \leq i \leq t+1,$ $b \in \Sigma$:

Say that $\delta(q, b) := (q_1, b_0, R $ or $L)$ and that $\delta(q, a_i) := (q_2, a_0, R$ or $L)$. We define $\delta_0: Q_0 \times \Sigma \to Q_0$ by

$\delta_0(q, (a_1,..,a_{t+1}), i) = \begin{cases} (q_2, (a_1,..,a_0,..,a_{t+1}), i+1) & \quad \text{if } R \text{ and }a_i \in \Gamma\\ (q_2, (a_1,..,a_0,..,a_{t+1}), i-1) & \quad \text{if } L \text{ and }a_i \in \Gamma\\ (q_1, (a_1,..,b_0,..,a_{t+1}), i+1) & \quad \text{if } R \text{ and }a_i = \sqcap \\ (q_2, (a_1,..,b_0,..,a_{t+1}), i-1) & \quad \text{if } L \text{ and }a_i = \sqcap\\ \end{cases} $

Where the change of letter in the $t+1$ tuple occured in the $i^{th}$ spot.

**Edit: also make the machine loop upon entering the accept or reject states

Then consider the DFA $A = (Q_0, \Sigma, \delta_0, g_0, F)$ where $g_0 = (q_0, (\sqcap,...,\sqcap), 1)$ and $F = \{(q_{accept}, x, j) : x \in \Gamma_0^{t+1}, 1 \leq j \leq t+1\}$

Now intuitively I think that this machine accepts $L$, but am having a hard time proving it.

So, is it true that $L(A) = L$? If so can you point some directions on how to prove it?

$\endgroup$
4
$\begingroup$

The language $L$ only depends on the first $t$ letters of the input (since the Turing machine never gets to any of the other letters). This implies that it is regular, since $$ L = (L \cap \Sigma^{<t}) \cup (L \cap \Sigma^t) \Sigma^*, $$ where $\Sigma^{<t} = \bigcup_{i=0}^{t-1} \Sigma^i$. The right-hand side is regular since $L \cap \Sigma^{<t}$ and $L \cap \Sigma^t$ are both finite, and so, regular.

$\endgroup$
  • $\begingroup$ thanks for the answer, but this isn't a complete proof, and it doesn't answer my question of whether the above construction is correct. How do you make this conclusion just from the fact that the language depends on the first $t$ letters of an input? Also would appreciate if you can look at my suggested answer. $\endgroup$ – Mariah May 16 '18 at 15:50
  • $\begingroup$ It can be turned to a complete proof. Your suggested proof looks too complicated. $\endgroup$ – Yuval Filmus May 16 '18 at 16:13
  • $\begingroup$ alright.. well, please don't be offended, but your answer has neither helped my attempt nor did it help me understand better the claim to be proved. $\endgroup$ – Mariah May 16 '18 at 16:31
  • 1
    $\begingroup$ Your answer tries to simulate the running of the Turing machine, but this is completely unnecessary. The essential point is that $L$ only depends on a constant length prefix of the input. $\endgroup$ – Yuval Filmus May 16 '18 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.