MAHARANA PRATAP GROUP OF INSTITUTIONS KOTHI
MANDHANA, KANPUR
(Approved by AICTE, New Delhi and Affiliated to Dr. AKTU, Lucknow)
Digital Notes
[Department of Computer Applications]
Subject Name : THEORY OF AUTOMATA &
FORMAL LANGUAGES
Subject Code : KCA 201
Course : MCA
Semester : II
Prepared by : Mr. Yogendra Singh
Reference No./MCA /Yogendra Singh/KCA 201/1/2
Page |1
UNIT-5: Turing Machine
Introduction to Turing Machine
➢ Turing machine was invented in 1936 by Alan Turing. It is an accepting device which
accepts Recursive Enumerable Language generated by type 0 grammar.
➢ Expressive Power of various Automata:
FA < DPDA < NPDA < LBA < TM
➢ It is similar to finite automata but with an unlimited and Unrestricted memory (tape)
➢ Turing machine can both write on the tape& read from the tape
➢ The read-write head of Turing machine can move to both left and write direction
➢ Turing machine has input tape of infinite length.
Turing machine Model
The Turing machine model is shown in figure. It is finite automaton connected to read-write head
with the following components:
1. Tape
2. Read-write head
3. Control unit
Page |2
Features of Turing Machine
There are various features of the Turing machine:
1. Turing machine is able to remember long sequence of input, because of infinite memory.
2. Input head can move left or right.
3. It has unlimited memory capability.
4. Turing Machine is more powerful among all.
Definition of Turing machine:
A Turing machine M is the described as a 7-tuple
M = (Q, Σ, Γ, δ, q0, B, F),
Where
1. Q is the set of internal states,
2. Σ is the input alphabet
3. Γ is the finite set of symbols called the tape alphabet,
4. δ is the transition function,
5. B is a special symbol called the blank,
6. q0 ∈ Q is the initial state,
7. F ⊆ Q is the set of final states.
In the definition of a Turing machine, we assume that Σ ⊆ Γ – { }, that is, that the input alphabet
is a subset of the tape alphabet, not including the blank. Blanks are ruled out as input for reasons
that will become apparent shortly. The transition function δ is defined as
Representation of Turing Machine(TM):
Page |3
Page |4
Example 01:Design a Turing machine for language L = {an bn | n≥ 1}
Example 02: The language L = {an bn cn | n≥ 1} is recognized by Turing machine
Solution:
Variation of Turing Machines
➢ Some modification to standard Turing machine
Page |5
➢ The variants are
1. Multi-tape Turing Machine
2. Non-deterministic Turing Machine
3. Multi-head Turing Machine
4. Multi-dimensional Turing machine
5. Multi-track Turing machine
1. Multi-tape Turing Machine
➢ A Turing machine with several tapes we call it a multi tape Turing machine.
➢ Every tape’s have their own Read/Write head
Figure: Multi-tape Turing Machine
➢ For n-tape Turing Machine
M = (Q, Σ, Γ, δ, q0, B, F),
We define
δ=Q x Γ n → Q x Γn x {L,R}n
2. Non Deterministic Turing Machine
It is similar to DTM except that for any input and current state it has a number of choices.
A string is accepted by a NDTM if there is a sequence of moves that leads to a final state
The Transition function −
δ =Q x Γ ->2Qx Γ x (L, R)
3. Multi-head Turing Machine
A multi-head Turing machine contains two or more heads to read the symbols on the same
tape
Page |6
Figure : multi-heads TM
4.Multi-dimensional Tape Turing Machine:
It has multi-dimensional tape where the head can move in any direction that is left,
right, up or down.
δ=Q x Γ → Q x Γ x {L,R, U, D}
5.Multi-track Tuirng machine:
6.Universal Turing Machine:
Page |7
➢ We have created different Turing Machine (T.M) for all different languages. This objection
can be overcome by designing a reprogrammable Turing machine, called a, universal
Turing machine. A universal Turing machine is a reprogrammable Turing machine which,
given as input the description of Turing machine M and a string w, can simulate the
computation of M on w
➢ A universal Turing machine is an automaton given a input the description of Turing
machine M , a string w can simulate the computation of m on w
➢ A universal Turing machine is a specified Turing machine that can simulate the behavior
of any Turing machine.
➢ A universal Turing machine has the structure of a multi-tape machine, as shown in figure
Figure: Universal Turing machine
Linear Bounded Automata:
A linear bounded automaton, like a standard Turing machine, has an unbounded tape, but how
much of the tape can be used is a function of the input. In particular, we restrict the usable part of
the tape to exactly the cells taken by the input. To enforce this, we can envision the input as
bracketed by two special symbols, the left-end marker [and the right-end marker]. For an input
w, the initial configuration of the Turing machine is given by the instantaneous description q0 [w].
The end marker cannot be rewritten, and the read-write head cannot move to the left of [ or to
the right of ]. We sometimes say that the read-write head “bounces” off the end markers.
A Turing machine that uses only the tape space occupied by the input is called a linear –bounded
automaton (LBA)
Page |8
➢ LBA = TM + Tape(input size)
➢ Expressive Power of various Automata:
FA < DPDA < NPDA < LBA < TM
➢ The language accepted by Linear bounded automata are said to be Context Sensitive
Language(CSL)
Church-Turing Thesis
➢ What is computable?
➢ Alonzo church – Lambda calculus
➢ Alan Turing – Turing machine
➢ A function on natural number is to computable by an algorithm if only if –it is computable
by Turing machine
➢ Everything that can be computed can be computed by a Turing machine
➢ Anything that can be done by digital computer can also be done by Turing machine
➢ Currently there is no problem which can be solved by computer and cannot solved by
Turing machine
Page |9
Recursive and Recursively Enumerable language
Definition
A language L is said to be recursively enumerable if there exists a Turing machine that accepts
it.
With qf a final state. The definition says nothing about what happens for w not in L; it may be that
the machine halts in a non final state or that it never halts and goes into an infinite loop. We can
be more demanding and ask that the machine tell us whether or not any given input is in its
language.
Definition:
A language L on Σ is said to be recursive if there exists a Turing machine M that accepts L and
that halts on every w in Σ+. In other words, a language is recursive if and only if there exists a
membership algorithm for it.
Halting machine
Halting machine that produces a ‘yes’ or ‘no’ in a finite amount of time. If the halting machine
finishes in a finite amount of time, the output comes as ‘yes’, otherwise as ‘no’.
The following is the block diagram of a Halting machine −
The following is the block diagram of an ‘Inverted halting machine’
P a g e | 10
Post Correspondence Problem (PCP):
➢ The Post Correspondence Problem (PCP) is an undecidable decision problem that was
introduced by Emil Post in 1946.
➢ The PCP problem over an alphabet ∑ is stated as follows −
Given the following two lists
A = w1, w2, w3, .... , wn
B = x1, x2, x3, .... xn
Then, instant of Post Correspondence Problem(PCP) has Solution,
if there is any sequence of integer i1,i2,………… im, m≥1
the condition wi1, wi2, wi3, .... win = xi1, xi2, xi3, .... xin satisfies.
Example 1
Find whether the lists
M = (ab, bab, bbaaa) and N = (a, ba, bab)
have a Post Correspondence Solution?
Solution
x1 x2
M ab bab
N a ba
In this case, there is no solution because −
| x2x1x3 | ≠ | y2y1y3 | (Lengths are not same)
Hence, it can be said that this Post Correspondence Problem is undecidable.
Example 2:
Consider the correspondence system as given below
A = (b, bab3, ba) and B = (b3, ba, a). The input set is ∑ = {0, 1}. Find the solution.
Solution:
A solution is 2, 1, 1, 3. That means w2w1w1w3 = x2x1x1x3
The constructed string from both lists is bab3b3a.
P a g e | 11
Example 3:
Does PCP with two lists x = (b, a, aba, bb) and y = (ba, ba, ab, b) have a solution?
Solution: Now we have to find out such a sequence that strings formed by x and y are identical.
Such a sequence is 1, 2, 1, 3, 3, 4. Hence from x and y list
P a g e | 12
