THEORY OF AUTOMATA

Mukesh Kumar Tripathi

Assistant Professor
Department of Information Technology
Vasavi College of Engineering
Turing Machines (contd.)
Formal Definition of a TM
Turing Machines (contd.)
Transition function
• One move (denoted by |---) in a TM does the following:
• (q, a) = (p, A, D)
• q is the current state
• a is the current tape symbol pointed by tape head a | A,D
q p
• After the move:
• State changes from q to p
• a is replaced with symbol A
• If D=“L”, the tape head moves “left” by one position.
Alternatively, if D=“R” the tape head moves “right” by one position.

You can also use:

 for R
 for L
Turing Machines (contd.)
Instantaneous Description of TM
• ID of a TM is defined in terms of the entire input string and the current state.
• Definition: An instantaneous description (ID) is a triple α1qα2, where:
• q, the current state, is in Q
• α1α2, is in Г*, and is the current tape contents up to the rightmost non-blank symbol,
or the symbol to the left of the tape head, whichever is rightmost
• The tape head is currently scanning the first symbol of α2
• At the start of a computation α1= ε
• If α2= ε then a blank is being scanned
Turing Machines (contd.)
Instantaneous Description of TM (contd.)
• Suppose the following is the current ID of a TM
X1X2…Xi-1qXiXi+1…Xm
means:
• q is the current state
• Tape head is pointing to Xi
• X1X2…Xi-1XiXi+1…Xn are the current tape symbols

Case 1) δ(q, Xi) = (p, A, L) then the next move is

X1X2…Xi-1 q XiXi+1…Xn |—

Case 2) δ(q, Xi) = (p, A, R) then the next move is

X1X2…Xi-1 q XiXi+1…Xn |—
Turing Machines (contd.)
Turing Machine as a Computing Device:
Example #1: Parity Checker Machine
Turing Machines (contd.)
Turing Machine as a Computing Device (contd.):
Example #1: Parity Checker Machine (contd.)
Turing Machines (contd.)
Turing Machine as a Computing Device (contd.):
Example #2: Design a TM for finding 1’s complement of a given number
Turing Machines (contd.)
Turing Machine as an Acceptor
• The TM can be considered as an accepting device accepting sets of strings.
• TM accepts type-0 languages or Recursively enumerable languages.
• When we consider TM as an accepting device, we usually consider a one-way infinite
tape.
• The TM consists of a one-way infinite read/write tape and a finite control.
Turing Machines (contd.)
Turing Machine as an Acceptor
Language of a TM:
• Let M be a TM. The language accepted is define by L(M)

L(M) = {w | w is in Ʃ*, q0w |—* α1 qf α2 , qf is in F, and α1, α2 are in Г*}

Turing Machines (contd.)
Turing Machine as an Acceptor
Example #1: Design a TM to accept L = {anbn | n >= 1}
Turing Machines (contd.)
Turing Machine as an Acceptor
Example #1 (contd.): TM to accept L = {anbn | n >= 1}
Turing Machines (contd.)
Turing Machine as an Acceptor
• Example #1 (contd.): TM to accept L = {anbn | n >= 1}
Turing Machines (contd.)
Turing Machine as an Acceptor
Example #1 (contd.): TM to accept L = {anbn | n >= 1} The TM basically matches up a’s and b’s
q1 is the “scan right” state
q2 is the “scan left” state
qf is the final state

Consider a string: aabb

Turing Machines (contd.)
Turing Machine as an Acceptor
Example #1 (contd.): TM to accept L = {anbn | n >= 1} The TM basically matches up a’s and b’s
q1 is the “scan right” state
q2 is the “scan left” state
qf is the final state

Consider a string: abb

Turing Machines (contd.)
Turing Machine as an Acceptor
• Example #2: Design a TM to accept set of all strings over{0, 1}.
Turing Machines (contd.)
Turing Machine as an Acceptor
• Example #3: Design a TM to accept L ={w | w is in {0, 1}* and w contains 000 as a substring}
Turing Machines (contd.)
Turing Machine as an Acceptor
• Example #3 (contd.): Design a TM to accept L ={w | w is in {0, 1}* and w contains 000 as a
substring}
Consider a string: 1010001
Turing Machines (contd.)
Turing Machine as an Acceptor
• Example #4: Design a TM for accepting strings of the language defined as {wwR | w is in
{0, 1}*}
Turing Machines (contd.)
Turing Machine as an Acceptor
• Example #4 (contd.): Design a TM for accepting strings of the language defined as {wwR |
w is in {0, 1}*}
 Programming Techniques for Turing Machines
• Designing a TM to solve a problem is an interesting task. It is somewhat similar to
programming.
• Given a problem, different TMs can be constructed to solve it.
• But, we would like to have a TM which does it in a simple and efficient manner.
• Techniques for TM Construction:
1. Storage in the State
2. Multiple Tracks
3. TM with Stationary Head
4. Subroutines
Programming Techniques for Turing Machines (contd.)
1. Storage in the State
Programming Techniques for Turing Machines (contd.)
2. Multiple Track TM
Programming Techniques for Turing Machines (contd.)
3. TM with Stationary Head
• In the definition of a TM, we defined (q, a) as (p, A, D), where D =L or R.
• So the head moves to the left or right after reading an input symbol.
• Suppose, we want to include the option that the head can continue to be in the same cell
for some input symbol.
• Then we define (q, a) as (p, A, S). This means that the TM, on reading the input symbol
a, changes the state to p and writes A in the current cell in place of a and continues to
remain in the same cell.
• In terms of IDs,
wqax |— wpAx
Programming Techniques for Turing Machines (contd.)
3. TM with Stationary Head (contd.)
(q, a) = (p, A, S).
• In terms of IDs,
wqax |— wpAx
• This move can be simulated by the standard TM with two moves.
Programming Techniques for Turing Machines (contd.)
4. Subroutines
• Just as a computer program has a main procedure and subroutines, the TM can also be
programmed to have a main TM and TMs which serve as subroutines.
• Suppose we have to make n copies of a word w. Input is #w# and the output is
#w#www…ww.
• In this case, we can write the mapping for a TM M sub which when started on #w# ends
of with #w#w.
• The main TM will call this Msub n times.
• In order that a TM M1 uses another TM M2 as a subroutine, the states of M1 and M2
have to be disjoint.
• Also, when M1 wants to call M2, from a state of M1, the control goes to the initial state
of M2.
• When the subroutine finishes and returns to M1, from the halting state of M2, the
machine goes to some state of M1.
Programming Techniques for Turing Machines (contd.)
4. Subroutines (contd.)
Programming Techniques for Turing Machines (contd.)
4. Subroutines (contd.)
 Extensions to the Basic TM
• Extended TM’s to be studied:
• Multi-tape Turing Machine
• Multi-head Turing Machine
• Nondeterministic Turing Machine
• Two-Dimensional Turing Machine
• The above extensions make no increase of the original TM’s power, but make
TM’s easier to use.
Extensions to the Basic TM (contd.)
1. Multi-tape TM
• A multi-tape TM is a TM, with k tapes each having a separate tape head.
• The move of this TM will depend on the state and symbol scanned by each head.
• In each tape, a symbol is printed on the cell scanned and each head can move
independently of the others.
Finite Control
control

Tape 1

Tape 2

Tape 3
Extensions to the Basic TM (contd.)
1. Multi-tape TM (contd.)
• Initially,
• the input string is placed on the 1st tape;
• the other tapes hold all blanks;
• the finite control is in its initial state;
• the head of the 1st tape is at the left end of the input;
• the tape heads of all other tapes are at arbitrary positions.
• A move consists of the following steps:
• the finite control enters a new state;
• on each tape, a new symbol is written in the cell under the tape head;
• each tape head moves left or right, or remains stationary.
Extensions to the Basic TM (contd.)
1. Multi-tape TM

FCinite
control

Tape 1 a

Tape 2 b

Tape 3 c
Extensions to the Basic TM (contd.)
Equivalence of One–tape & Multi-tape TM’s
Theorem: Every language accepted by a k-tape TM is also accepted by a single-tape
TM
• Proof:
• Construct a single-tape TM with 2k tracks, where each tape of the k-tape TM is
simulated by 2 tracks of basic TM
• k out of the 2k tracks simulate the k input tapes
• The other k out of the 2k tracks keep track of the k tape head positions
Extensions to the Basic TM (contd.)
Equivalence of One–tape & Multi-tape TM’s (contd.)
• To simulate one move of the k-tape TM, the single tape TM makes two sweeps, one from
left to right and another from right to left:
• It starts on the leftmost cell, which contains a X in one of the odd tracks.
• While moving from left to right, when it encounters a X, it stores the symbol below it
in its finite control.
• It keeps a counter as one of the component of the state to check whether it has read
the symbols from all the tapes.
• After the left to right move is over, depending on the move of multi-tape TM
determined by the symbols read, the single tape TM makes a right to left sweep
changing the corresponding symbols on the even tracks and positioning the X’s
properly in the odd-numbered tracks.
Extensions to the Basic TM (contd.)
Equivalence of One–tape & Multi-tape TM’s
Extensions to the Basic TM (contd.)
Equivalence of One–tape & Multi-tape TM’s
Extensions to the Basic TM (contd.)
2. Multi-head TM
• A multi-head TM is a single tape TM having k heads reading symbols on the same tape.
• A move of this TM depends on the state and on the symbol scanned by each head.
• In one move, the TM can change the state, write a new symbol on the cell scanned by
each head, and can move each head left, right, or remains stationary.
Extensions to the Basic TM (contd.)
Equivalence of multi–head & single head TM’s
Theorem: A multi-head TM M can be simulated by a single head TM M’.
• Proof:
• Let M have k heads. Then, M’ will have k+1 tracks on a single tape.
• One track will contain the contents of the tape of M and the other tracks are used to mark the head
positions.
• One move of M is simulated by M’ by making a left to right sweep followed by a right to left
sweep.
• The simulation is similar to the one given for multi-tape TM.
• One fact about which one has to be careful here is the time when two heads scan the same symbol
and try change it differently. In this case, some priority among heads has to be used.
Extensions to the Basic TM (contd.)
3. Nondeterministic TM’s
• Transition function:
: Q    2(Q    {L, R})
• A nondeterministic TM (NTM) has multiple choices of next moves, i.e.,
(q, a) = {(p1, A1, D1), (p2, A2, D2), …, (pk, Ak, Dk)}.
• The computation of any input will be in several directions and the input is accepted if there
is at least one sequence of moves which accepts it.
• If MN is NTM, then there is a DTM MD such that L(MN) = L(MD).
Extensions to the Basic TM (contd.)
4. Two-Dimensional TM
• The TM can have two dimensional tapes.
• When the head is scanning a symbol, it can move left, right, up or down.
 Restricted TMs
• We can discuss some more variations of TMs, which are in the form of restrictions.
• Restricted TMs to be studied:
• the tape is infinite only to the right (“TM with semi-infinite tape”),
• the tapes are only used as stacks (“stack machines”);
• the stacks are used as counters only (“counter machines”).
• The above restrictions make no decrease of the original TM’s power, but are useful for
theorem proving.
Restricted TM’s (contd.)
1. TM’s with Semi-infinite Tapes
• The two-way infinite tape is equivalent to one way infinite tape.
Restricted TM’s (contd.)
1. TM’s with Semi-infinite Tapes (contd.)
Simulating two-way infinite tape with one way infinite tape:
• Use two tracks on the semi-infinite tape.
• The upper track represents the cells of the original TM that are at or to the right of the
initial head position.
• The lower track represents the positions left of the initial position, but in reverser order.
Restricted TM’s (contd.)
2. Multi-stack Machines
• Multi-stack machines, which are restricted versions of TM’s, may be regarded as
extensions of pushdown automata (PDA’s).
• What happens when we give the PDA several stacks.
• A TM can accept languages that are not accepted by any PDA with one stack.
• Actually, a PDA with two stacks has the same computation power as the TM.
• Theorem:
If a language is accepted by a TM, then it is accepted by a two-stack machine.
Restricted TM’s (contd.)
2. Multi-stack Machines (contd.)
• A k-stack machine is a deterministic PDA with k stacks.
• The multistack machine has a finite control, which is in one of a finite set of states.
• It has a finite stack alphabet, which it uses for all its stacks.
• A move of the multistack machine is based on:
1. The state of the finite control
2. The input symbol read, which is chosen from the finite input alphabet.
3. The top stack symbol on each of its stacks.
• In one move, the multistack machine can:
a) Change to a new state
b) Replace the top symbol of each stack with a string of zero or more stack symbols.
Restricted TM’s (contd.)
2. Multi-stack Machines (contd.)
Restricted TM’s (contd.)
3. Counter Machines
• A counter machine may be thought of in one of two ways:
• Way 1: The counter machine has the same structure as the multi-stack machine, but in
place of each stack is a counter.
• A counter holds any nonnegative integer.
• The machine can only distinguish zero and nonzero counters.
• In one move, the counter machine can:
• changing the state;
• add or subtract 1 from any of its counters, independently. However, a counter
is not allowed to become negative, so it cannot subtract 1 from a counter that
is currently 0.
Restricted TM’s (contd.)
3. Counter Machines (contd.)
• Way 2: A counter machine may also be regarded as a restricted multi-stack machine.
The restrictions are as follows:
• There are only two stack symbols Z0 and X.
• Z0 is initially on each stack.
• Can replace Z0 only by a string of the form XiZ0 for some i  0.
• Can replace X only by Xi for some i  0. That is, Z0 appears only on the bottom
of each stack, and all other stack symbols, in any, are X.