BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
Module 5
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.
There are various features of the Turing machine:
1. It has an external memory which remembers arbitrary long sequence of input.
2. It has unlimited memory capability.
3. The model has a facility by which the input at left or right on the tape can be read easily.
4. The machine can produce a certain output based on its input. Sometimes it may be required
that the same input has to be used to generate the output. So, in this machine, the
distinction between input and output has been removed. Thus, a common set of alphabets
can be used for the Turing machine.
Formal definition of Turing machine
A Turing machine can be defined as a collection of 7 components:
Q: the finite set of states
∑: the finite set of input symbols
T: the tape symbol
q0: the initial state
F: a set of final states
B: a blank symbol used as a end marker for input
δ: a transition or mapping function.
The mapping function shows the mapping from states of finite automata and input symbol on the
tape to the next states, external symbols and the direction for moving the tape head. This is known
as a triple or a program for turing machine.
(q0, a) → (q1, A, R)
That means in q0 state, if we read symbol 'a' then it will go to state q1, replaced a by X and move
ahead right(R stands for right).
Example: Construct TM for the language L ={0n1n} where n>=1.
Solution:
We have already solved this problem by PDA. In PDA, we have a stack to remember the previous
symbol. The main advantage of the Turing machine is we have a tape head which can be moved
forward or backward, and the input tape can be scanned.
The simple logic which we will apply is read out each '0' mark it by A and then move ahead along
with the input tape and find out 1 convert it to B. Now, repeat this process for all a's and b's.
Now we will see how this turing machine work for 0011.
The simulation for 0011 can be shown as below:
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
Now, we will see how this turing machine will works for 0011. Initially, state is q0 and head
points to 0 as:
The move will be δ(q0, 0) = δ(q1, A, R) which means it will go to state q1, replaced 0 by A and
head will move to the right as:
The move will be δ(q1, 0) = δ(q1, 0, R) which means it will not change any symbol, remain in
the same state and move to the right as:
The move will be δ(q1, 1) = δ(q2, B, L) which means it will go to state q2, replaced 1 by B and
head will move to left as:
Now move will be δ(q2, 0) = δ(q2, 0, L) which means it will not change any symbol, remain in
the same state and move to left as:
The move will be δ(q2, A) = δ(q0, A, R), it means will go to state q0, replaced A by A and head
will move to the right as:
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
The move will be δ(q0, 0) = δ(q1, A, R) which means it will go to state q1, replaced 0 by A, and
head will move to right as:
The move will be δ(q1, B) = δ(q1, B, R) which means it will not change any symbol, remain in
the same state and move to right as:
The move will be δ(q1, 1) = δ(q2, B, L) which means it will go to state q2, replaced 1 by B and
head will move to left as:
The move δ(q2, B) = (q2, B, L) which means it will not change any symbol, remain in the same
state and move to left as:
Now immediately before B is A that means all the 0?s are market by A. So we will move right to
ensure that no 1 is present. The move will be δ(q2, A) = (q0, A, R) which means it will go to state
q0, will not change any symbol, and move to right as:
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
The move δ(q0, B) = (q3, B, R) which means it will go to state q3, will not change any symbol,
and move to right as:
The move δ(q3, B) = (q3, B, R) which means it will not change any symbol, remain in the same
state and move to right as:
The move δ(q3, Δ) = (q4, Δ, R) which means it will go to state q4 which is the HALT state and
HALT state is always an accept state for any TM.
The same TM can be represented by Transition Diagram.
Basic Model of Turing machine
The turning machine can be modelled with the help of the following representation.
1. The input tape is having an infinite number of cells, each cell containing one input symbol
and thus the input string can be placed on tape. The empty tape is filled by blank characters.
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
2. The finite control and the tape head which is responsible for reading the current input symbol.
The tape head can move to left to right.
3. A finite set of states through which machine has to undergo.
4. Finite set of symbols called external symbols which are used in building the logic of turing
machine.
Language accepted by Turing machine
The turing machine accepts all the language even though they are recursively enumerable.
Recursive means repeating the same set of rules for any number of times and enumerable means
a list of elements. The TM also accepts the computable functions, such as addition, multiplication,
subtraction, division, power function, and many more.
Example: Construct a turing machine which accepts the language of aba over ∑ = {a, b}.
Solution:
We will assume that on input tape the string 'aba' is placed like this:
The tape head will read out the sequence up to the Δ characters. If the tape head is readout 'aba'
string then TM will halt after reading Δ.
Now, we will see how this turing machine will work for aba. Initially, state is q0 and head points
to a as:
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
The move will be δ(q0, a) = δ(q1, A, R) which means it will go to state q1, replaced a by A and
head will move to right as:
The move will be δ(q1, b) = δ(q2, B, R) which means it will go to state q2, replaced b by B and
head will move to right as:
The move will be δ(q2, a) = δ(q3, A, R) which means it will go to state q3, replaced a by A and
head will move to right as:
The move δ(q3, Δ) = (q4, Δ, S) which means it will go to state q4 which is the HALT state and
HALT state is always an accept state for any TM.
The same TM can be represented by Transition Table:
States a b Δ
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
q0 (q1, A, R) – –
q1 – (q2, B, R) –
q2 (q3, A, R) – –
q3 – – (q4, Δ, S)
q4 – – –
The same TM can be represented by Transition Diagram:
Examples of TM
Example 1: Construct a TM for the language L = {0n1n2n} where n≥1
Solution:
L = {0n1n2n | n≥1} represents language where we use only 3 character, i.e., 0, 1 and 2. In this,
some number of 0's followed by an equal number of 1's and then followed by an equal number of
2's. Any type of string which falls in this category will be accepted by this language.
The simulation for 001122 can be shown as below:
Now, we will see how this Turing machine will work for 001122. Initially, state is q0 and head
points to 0 as:
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
The move will be δ(q0, 0) = δ(q1, A, R) which means it will go to state q1, replaced 0 by A and
head will move to the right as:
The move will be δ(q1, 0) = δ(q1, 0, R) which means it will not change any symbol, remain in
the same state and move to the right as:
The move will be δ(q1, 1) = δ(q2, B, R) which means it will go to state q2, replaced 1 by B and
head will move to right as:
The move will be δ(q2, 1) = δ(q2, 1, R) which means it will not change any symbol, remain in
the same state and move to right as:
The move will be δ(q2, 2) = δ(q3, C, R) which means it will go to state q3, replaced 2 by C and
head will move to right as:
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
Now move δ(q3, 2) = δ(q3, 2, L) and δ(q3, C) = δ(q3, C, L) and δ(q3, 1) = δ(q3, 1, L) and δ(q3,
B) = δ(q3, B, L) and δ(q3, 0) = δ(q3, 0, L), and then move δ(q3, A) = δ(q0, A, R), it means will
go to state q0, replaced A by A and head will move to right as:
The move will be δ(q0, 0) = δ(q1, A, R) which means it will go to state q1, replaced 0 by A, and
head will move to right as:
The move will be δ(q1, B) = δ(q1, B, R) which means it will not change any symbol, remain in
the same state and move to right as:
The move will be δ(q1, 1) = δ(q2, B, R) which means it will go to state q2, replaced 1 by B and
head will move to right as:
The move will be δ(q2, C) = δ(q2, C, R) which means it will not change any symbol, remain in
the same state and move to right as:
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
The move will be δ(q2, 2) = δ(q3, C, L) which means it will go to state q3, replaced 2 by C and
head will move to left until we reached A as:
immediately before B is A that means all the 0's are market by A. So we will move right to ensure
that no 1 or 2 is present. The move will be δ(q2, B) = (q4, B, R) which means it will go to state q4,
will not change any symbol, and move to right as:
The move will be (q4, B) = δ(q4, B, R) and (q4, C) = δ(q4, C, R) which means it will not change
any symbol, remain in the same state and move to right as:
The move δ(q4, X) = (q5, X, R) which means it will go to state q5 which is the HALT state and
HALT state is always an accept state for any TM.
The same TM can be represented by Transition Diagram:
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
Example 2: Construct a TM machine for checking the palindrome of the string of even
length.
Solution:
Firstly, we read the first symbol from the left and then we compare it with the first symbol from
right to check whether it is the same.
Again, we compare the second symbol from left with the second symbol from right. We repeat
this process for all the symbols. If we found any symbol not matching, we cannot lead the machine
to HALT state.
Suppose the string is ababbabaΔ. The simulation for ababbabaΔ can be shown as follows:
Now, we will see how this Turing machine will work for ababbabaΔ. Initially, state is q0 and head
points to a as:
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
We will mark it by * and move to right end in search of a as:
We will move right up to Δ as:
We will move left and check if it is a:
It is 'a' so replace it by Δ and move left as:
Now move to left up to * as:
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
Move right and read it
Now convert b by * and move right as:
Move right up to Δ in search of b as:
Move left, if the symbol is b then convert it into Δ as:
Now move left until * as:
Replace a by * and move right up to Δ as:
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
We will move left and check if it is a, then replace it by Δ as:
It is 'a' so replace it by Δ as:
Now move left until *
Now move right as:
Replace b by * and move right up to Δ as:
Move left, if the left symbol is b, replace it by Δ as:
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
Move left till *
Move right and check whether it is Δ
Go to HALT state
The same TM can be represented by Transition Diagram:
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
Example 3: Construct a TM machine for checking the palindrome of the string of odd
length.
Solution:
Firstly, we read the first symbol from left and then we compare it with the first symbol from
right to check whether it is the same.
Again, we compare the second symbol from left with the second symbol from right. We repeat
this process for all the symbols. If we found any symbol not matching, we lead the machine to
HALT state.
Suppose the string is 00100Δ. The simulation for 00100Δ can be shown as follows:
Now, we will see how this Turing machine will work for 00100Δ. Initially, state is q0 and head
points to 0 as:
Now replace 0 by * and move right as:
Move right up to Δ as:
Move left and replace 0 by Δ and move left:
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
Now move left up to * as:
Move right, convert 0 by * and then move right as:
Moved right up to Δ
Move left and replace 0 by Δ as:
Move left till * as:
Move right and convert 1 to * as:
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
Move left
Since it is *, goto HALT state.
The same TM can be represented by Transition Diagram:
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
Variants of Turing Machine:
1.
2.
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
3.
4.
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
Non-deterministic Turing Machine
➢ A non-deterministic Turing machine (NDTM) differs from a deterministic
Turing machine in that it can transition into multiple possible states from a given
state and symbol. Instead of following a single path, the NDTM can explore
many computational paths simultaneously.
➢ Example
➢ Consider the language L = {0n 1m} where n and m are not necessarily equal. An
NDTM can non-deterministically choose how many 0's and 1's to match,
accepting the string if it satisfies the condition.
➢ Every non-deterministic Turing machine has an equivalent deterministic Turing
machine. The deterministic version simulates all possible paths of the NDTM
and accepts the string if any path leads to an accepting state.
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
Undecidability and the Universal and Diagonalization Languages
➢ Undecidability refers to problems for which no algorithm can definitively
provide a "yes" or "no" answer for all possible inputs. The universal language
(Lu) is a specific example of an undecidable language that is accepted by a
Turing machine but not decidable, and the diagonalization language (Ld) is an
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
example of a non-recursively enumerable language
1. Undecidability:
➢ A problem is considered undecidable if there's no algorithm (or Turing machine)
that can always determine the correct answer (yes or no) for all possible instances
of that problem, according to DigitalBitHub.
➢ The concept of undecidability is fundamental in theoretical computer science,
revealing limitations on what can be computed algorithmically.
2. The Universal Language (Lu):
➢ The universal language Lu is defined as the set of all pairs of Turing machines
and input strings where the machine accepts the string.
➢ Lu is accepted by a universal Turing machine (U), which can simulate any other
Turing machine.
➢ Despite being accepted by a Turing machine (U), Lu is still undecidable. This
means there's no algorithm to determine, for any given machine and input,
whether that machine will halt and accept the input.
3. The Diagonalization Language (Ld):
➢ The diagonalization language Ld is constructed by considering the behavior of
Turing machines on their own encodings. It contains strings where the machine,
when given its own encoding as input, does not halt or accept.
➢ Ld is an example of a language that is not recursively enumerable, meaning there
is no Turing machine that can list all the strings in Ld.
➢ The diagonalization technique is used to demonstrate the existence of languages
that are not recursively enumerable, according to Columbia University Computer
Science Department.
4. Relation between Lu and Ld:
➢ The diagonalization language (Ld) is used to prove that the universal language
(Lu) is undecidable. This is achieved by showing that if Lu were decidable, then
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
a contradiction could be derived by creating a machine that simulates the
behavior of other machines on their own encodings.
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
Rice's theorem:
Any nontrivial property about the language recognized by a Turing machine is undecidable.
A property about Turing machines can be represented as the language of all Turing machines, encoded
as strings, that satisfy that property. The property P is about the language recognized by Turing
machines if whenever L(M)=L(N) then P contains (the encoding of) M iff it contains (the encoding
of) N. The property is non-trivial if there is at least one Turing machine that has the property, and at
least one that hasn't.
Proof: Without limitation of generality we may assume that a Turing machine that recognizes the
empty language does not have the property P. For if it does, just take the complement of P. The
undecidability of that complement would immediately imply the undecidability of P.
In order to arrive at a contradiction, suppose P is decidable, i.e. there is a halting Turning machine B
that recognizes the descriptions of Turing machines that satisfy P. Using B we can construct a Turning
machine A that accepts the language {(M,w)| M is the description of a Turing machine that accepts
the string w}. As the latter problem is undecidable this will show that B cannot exists and P must be
undecidable as well.
Let MP be a Turing machine that satisfies P (as P is non-trivial there must be one). Now A operates
as follows:
1. On input (M,w), create a (description of a) Turing machine C(M,w) as follows:
1. On input x, let the Turing machine M run on the string w until it accepts (so if it doesn't
accept C(M,w) will run forever).
2. Next run MP on x. Accept iff MP does.
2. Note that C(M,w) accepts the same language as MP if M accepts w; C(M,w) accepts the empty
language if M does not accept w.
3. Thus if M accepts w the Turing machine C(M,w) has the property P, and otherwise it doesn't.
4. Feed the description of C(M,w) to B. If B accepts, accept the input (M,w); if B rejects, reject.
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat
BRAINWARE UNIVERSITY
[PCC-CSM404] [Formal Language and Automata Theory]
2024-25 Prepared by: Faculties of Department of CSE-AI, Brainware University,
Barasat