0
$\begingroup$

I am looking to create a single tape acceptor Turing machine acting upon the language of any ASCII string, that would only accept strings that contains at least five G's and at most three T's, and rejects any other ASCII string input. I am kind of stuck on how the machine would know that it had encountered greater than or equal to five G's and less than or equal to three T's.

$\endgroup$
1
  • $\begingroup$ What about some states that remember how many Gs ad Ts you have read? :) $\endgroup$ Jan 19, 2021 at 10:34

1 Answer 1

2
$\begingroup$

In general, whenever you try to design a machine accepting a language with this kind of "finite conditions", the easiest solution is to hard-code those conditions directly into the states of your machine.

Here, you would have 24 "counting" states, labelled by $(g, t)$ for $0 \leq g \leq 5$ and $0 \leq t \leq 3$. Whenever you read some $G$ while already in state $(g, t)$, you move on to the corresponding state $(g+1, t)$ (and if you read a $T$, you go to $(g, t+1)$). Otherwise, you simply loop on your current state.

Now, you have to enforce your conditions: if you read a $T$ while in a state $(g, 3)$, you reject the word, and if your word end while you are in a state $(g, t)$ with $g < 5$, you reject too.

Of course, there is probably some technical details to work out precisely, and there might exist some clever and trickier ideas to do this, but this method is easy to understand and can be immediately generalised to all the problems of this kind.

$\endgroup$
1
  • $\begingroup$ I figured it out; I had 18 states instead, and what I basically did was have the "read-write" head start over whenever it found a G first, and whenever it found one it would overwrite it with some letter. If it finds no more G's before reaching 5 G's then reject. I did something similar for T's too, after it finds at least 5 G's if that makes sense. $\endgroup$ Jan 20, 2021 at 23:06

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.