0
$\begingroup$

A Forgetful Turing Machine (FTM) operates just like a normal Turing machine except that, in every instruction (i.e., transition), the letter written in the tape cell is always the letter $a$, regardless of the current state and the current letter (although the read/write head is still allowed to move either Left or Right, according to the instruction). What class of languages is recognised by FTMs?

Is the language non-empty with only the letter $a$? Does this mean that it is regular since it can be represented by $aa^*$?

$\endgroup$
  • 2
    $\begingroup$ Your model can certainly simulate DFAs. Make sure you understand the definition of the language accepted by a forgetful Turing machine. $\endgroup$ – Yuval Filmus Sep 22 at 13:52
  • $\begingroup$ @YuvalFilmus since DFAs recognises regular languages, this also implies that FTMs is recognised by a regular language, right? $\endgroup$ – llamaro25 Sep 22 at 14:02
  • $\begingroup$ I’d say the implication goes the opposite way. $\endgroup$ – Yuval Filmus Sep 22 at 16:33
  • $\begingroup$ This is an interesting and somewhat tricky question but you seem not to understand the basic definition of a language recognized by a machine. Maybe it is better to ask the one who assigns this question to you for help. $\endgroup$ – xskxzr Sep 22 at 18:42
  • $\begingroup$ @xskxzr I did but I still did not understand. Are there any hints on how to approach this question? $\endgroup$ – llamaro25 Sep 23 at 6:54
0
$\begingroup$

The class languages recognized by FTMs are the class of regular languages. A FTM can completely simulate a DFA, so each regular language can be recognized by a FTM. On the other hand, if we can prove each FTM recognizes a regular language, we have proved the assertion.

Given a FTM $F$ with the set of states $Q$, we use the Myhill–Nerode theorem to show the language it recognizes is regular. Given a string $x$, we ask the following query:

  1. If $F$ runs on $x$, does $F$ ever leave $x$ to the right? If so, in which state is $F$ when it first moves to the first position to the right of $x$? If not, does $F$ accept $x$?

... and the following $|Q|$ queries for each state $q\in Q$:

  1. If $F$ runs on $\underbrace{a\cdots a}_\text{the number of $a$ = $|x|$}$, but is started on the rightmost $a$ and in state $q$, does $F$ ever leave the input to the right? If so, in which state is $F$ when it first moves to first position to the right of the input? If not, does $F$ accept the input finally?

We collect the strings that give the same answers to the $|Q|+1$ queries above into the same class. Since there are $(|Q|+2)^{|Q|+1}$ possible answers to the $|Q|+1$ queries above, there are only finite many classes. Next, we are going to prove that for any strings $x,y$ in the same class, i.e., that give the same answers to the $|Q|+1$ queries, for any string $z$, $F$ accepts either both or neither of $xz$ and $yz$, which completes the proof by the Myhill–Nerode theorem.

Consider that $F$ runs respectively on $xz$ and $yz$. Note the answers to query 1 are the same for $x$ and $y$, there are two cases:

  1. $F$ never leaves $x$ to the right on $xz$, and $F$ never leaves $y$ to the right on $yz$. In this case, $F$ runs as if the inputs are respectively $x$ and $y$. Since the answers to query 1 are the same for $x$ and $y$, $F$ accepts either both or neither of $xz$ and $yz$.
  2. $F$ ever leaves $x$ to the right on $xz$, and $F$ ever leaves $y$ to the right on $yz$. In this case, $F$ is in the same state when it first moves to the leftmost position of $z$, so $F$ behaves the same until it returns respectively to the rightmost position of $x$ and $y$. According to the definition of FTM, the input must become $a\cdots a$ when $F$ returns, and we can apply a recursive analysis according to query 2 (you can use mathematical induction to write a strict proof). As a result, $F$ accepts either both or neither of $xz$ and $yz$.

Of course, the analysis above assumes the tape of the FTM is restricted such that the head cannot leave the input to the left. The proof is similar without this assumption.

$\endgroup$

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.