0
$\begingroup$

Question Description

I’m facing a problem asking me to construct a (deterministic) Turing Machine that can accept such a language:

$L = \{ w \in \{a,b\}^* \mid \mbox{for any non-empty prefix $w'$ of $w$}, n_a(w') > n_b(w')\}$

The problem isn’t expressed in English originally. To make sure I’m translating correctly, I’ll provide some example:

$a \in L$, $ab \notin L$, $aab \in L$, $aabb \notin L$, $aabab \in L$, $aababb \notin L$

What I’ve done so far

We have an existing Turing machine which can accept a string that contains same number of ‘a’ and ‘b’ (I.e. $n_a(w) = n_b(w)$). I think it might be possible to modify this one to solve my problem, so I wrote this:

# pip install automata-lib
from automata.tm.dtm import DTM

machine = DTM(
    states={'q0', 'q1', 'q2', 'q3'},
    input_symbols={'a', 'b'},
    tape_symbols={'a', 'b', 'x', 'y', '.'},
    transitions={
        'q0': {
            'a': ('q1', 'x', 'R'),
            'y': ('q0', 'y', 'R')
        },
        'q1': {
            'a': ('q1', 'a', 'R'),
            'b': ('q2', 'y', 'L'),
            'y': ('q1', 'y', 'R'),
            '.': ('q3', '.', 'L'),
        },
        'q2': {
            'a': ('q2', 'a', 'L'),
            'x': ('q0', 'x', 'R'),
            'y': ('q2', 'y', 'L'),
        }
    },
    initial_state='q0',
    blank_symbol='.',
    final_states={'q3'}
)

I’m providing this python code because it’s easy to run and test. Those transitions can be explained as: $\delta(q_0, a) = (q_1,x,R)$ and so on.

This DTM can accept any string that begin with ‘a’ and have more ‘a’ than ‘b’. However, it doesn’t meet the condition “any prefix”. I’m stuck right here, can somebody give me a hint?

$\endgroup$
2
  • $\begingroup$ The description of a Turing machine that solves your problem using two tapes is quite simple. Would you be happy with that? Of course you can always design a single-tape TM either by reducing two tapes to one using standard techniques or by an ad-hoc solution, but this would be more tedious $\endgroup$
    – Steven
    Commented Nov 4, 2022 at 15:53
  • $\begingroup$ @Steven A two tape machine would be fine! I can modify it by myself. $\endgroup$
    – Morphlng
    Commented Nov 5, 2022 at 8:11

1 Answer 1

0
$\begingroup$

You can build a two-tape Turing machine quite easily. The first tape will contain the input string, while the second tape will act as a counter.

The machine will work in at most $|w|$ phases, indexed from $1$. In the generic $i$-th phase it will check that $n_a(w_i) > n_b(w_i)$, where $w$ is the prefix of the input containing the first $i$ symbols.

During this process, the second tape will contain only $c$s (the specific symbol is not important, I'm using $c$ for the sake of readability) and its head will be placed on the last $c$ (if any). We will preserve the following invariant: at the end of the $i$-th phase, the number of $c$s on the second tape will be exactly $n_a(w_i) - n_b(w_i)$. As soon as this quantity becomes $0$ (i.e., the tape becomes empty), the machine rejects. If $|w|$ phases are completed (i.e., the whole input has been processed) and the second tape is not empty, the machine accepts.

The machine works as follows:

  1. If the current (i.e., first) symbol on the first tape is not $a$, reject.
  2. If the current symbol on the first tape is blank, accept.
  3. If the current symbol on the first tape is $a$:
    • Move the second head to the right.
    • Write $c$ on the second tape.
  4. If the current symbol on the first tape is $b$:
    • Write a blank on the second tape.
    • Move the second head to the left.
  5. If the current symbol on the second tape is blank, reject.
  6. Move the first head to the right and repeat from step 2.
$\endgroup$
3
  • $\begingroup$ Hi,@Steven! I have a question about how the two-taped machine works. In step 3, you described as “move first, then write”, but in step 4 the machine “write first, then move”. I’m not sure if that can be different? In our textbook, it is always “write first, then move”. If it can be different, how to rewrite in transition form? (Simply $\delta(q_0,a,.) = (q_0,a,R,c,R)$?) $\endgroup$
    – Morphlng
    Commented Nov 11, 2022 at 6:02
  • $\begingroup$ A single transition writes and them moves. But you can always simulate "move then write" with multiple transitions. Suppose you are in state $q_0$ reading $x$ and want to move left, write $y$, and transition to state $q_1$. You can do the following: 1) write $X$ (so that the current symbol is unchanged), move left, transition to an intermediate state $q'_1$, 2) when you are in state $q'_1$ reading an arbitrary symbol $z$, you write $y$, keep the head in place, and transition to $q_1$. $\endgroup$
    – Steven
    Commented Nov 11, 2022 at 10:05
  • $\begingroup$ The transitions for a one-tape Turing machine would be: $\delta(q_0, x) = (q'_1, x, L)$ and $\delta(q'_1, z) = (q_1, y, S)$ (where $L$ stands for "left" and $S$ stands for "stay") for all $z$. For a two-tape Turing machine that is in state $q_0$, reading $x_1$ and $x_2$, and wants to "write-then-move" in order to write $y$ on the preceding tape cell of the second tape, while leaving the first tape unchanged: $\delta(q_0, (x_1, x_2)) = (q'_1, (x_1, x_2), (S, L))$ and $\delta(q'_1, (z_1, z_2)) = (q_1, (z_1, y), (S, S))$ for all $(z_1, z_2)$. $\endgroup$
    – Steven
    Commented Nov 11, 2022 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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