​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ Module-5

1. Design a Turing Machine for L={a ^ n b ^ n ∣n≥1}

Algorithm
Scan from left and replace first a by X.
Move right until first unmarked b is found.
Replace b by Y.
Move left to the beginning of the tape.
Repeat Steps 1–4.
If all a's and b's are marked, accept.
If an unmatched symbol is found, reject.
Example:-Input:
​ aaabbb
​ Steps:
​ aaabbb
​ XaabYb
​ XXaYYb
​ XXXYYY
Diagm:-q0 --a/X,R--> q1
q1 --a,R--> q1
q1 --Y,R--> q1
q1 --b/Y,L--> q2
q2 --a,L--> q2
q2 --X,L--> q2
q2 --Y,L--> q2
q2 --B,R--> q0
q0 --Y,R--> q3
q3 --Y,R--> q3
q3 --B--> qaccept
2. Design a Turing Machine for L={a^nb^nc^n∣n≥1}
Algorithm
Replace first a by X.
Move right and replace corresponding b by Y.
Move right and replace corresponding c by Z.
Return to the leftmost unmarked a.
Repeat until all symbols are marked.
Accept if only X, Y, Z remain.
Example
Input:aaabbbccc
Steps:-
aaabbbccc
XaYbbZcc
XXYYbbZZc
XXXYYYZZZ
Diagm:-
q0 --a/X,R--> q1
q1 --a,R--> q1
q1 --Y,R--> q1
q1 --b/Y,R--> q2
q2 --b,R--> q2
q2 --Z,R--> q2
q2 --c/Z,L--> q3
q3 --X,L--> q3
q3 --Y,L--> q3
q3 --Z,L--> q3
q3 --B,R--> q0
q0 --Y,R--> q4
q4 --Y,R--> q4
q4 --Z,R--> q4
q4 --B--> qaccept
3. Design a Turing Machine for Palindrome
A palindrome reads the same forward and backward.
Examples:
abba
aba
Algorithm
Read the first symbol.
Mark it (X).
Move to the right end.
Check whether the last symbol matches.
If matched, mark it (X).
Return to the left.
Repeat for remaining symbols.
Accept if all symbols are matched.
Example:-Input:
abba
Steps:
abba
XbbX
XXbX
XXXX
Accepted.
State Diagram (Simplified)
q0 --a/X,R--> q1
q1 --a,b,R--> q1
q1 --B,L--> q2
q2 --a/X,L--> q3
q3 --a,b,L--> q3
q3 --B,R--> q0
q0 --B--> qaccept
[Link] a Turing Machine for Equal Number of a's and b's
L={w∣na(w)=nb(w)}
Algorithm
Scan the tape from left to right.
Find the first unmarked a and replace it with X.
Move right and find an unmarked b and replace it with Y.
Return to the beginning of the tape.
Repeat Steps 2–4.
If all a's and b's are marked (X and Y only), ACCEPT.
If an unmatched a or b remains, REJECT.
Example:-
Input:
aabb
Step 1:
XaYb
Step 2:
XXYY
All symbols matched.(ACCEPT)
State Diagram
q0 --a/X,R--> q1
q1 --a,R--> q1
q1 --Y,R--> q1
q1 --b/Y,L--> q2
q2 --a,L--> q2
q2 --X,L--> q2
q2 --Y,L--> q2
q2 --B,R--> q0
q0 --X,R--> q0
q0 --Y,R--> q0
q0 --B--> qaccept
Transition Table:-
| Present State | Read | Write | Move | Next State |
| ------------- | ---- | ----- | ---- | ---------- |
| q0 | a | X | R | q1 |
| q1 | a | a | R | q1 |
| q1 | Y | Y | R | q1 |
| q1 | b | Y | L | q2 |
| q2 | a | a | L | q2 |
| q2 | X | X | L | q2 |
| q2 | Y | Y | L | q2 |
| q2 | B | B | R | q0 |
| q0 | B | B | S | qaccept |
[Link] a Turing Machine for Binary Addition (Unary Addition)
Algorithm
Scan the tape and locate the symbol +.
Replace + with 1.
Move to the right end of the tape.
Delete one extra 1 from the second number.
Continue until all symbols after + are merged.
Accept when only one block of 1s remains.
TM Representation
States
q0 = Start State
q1 = Search +
q2 = Shift symbols
qaccept = Final State
Transition Table
State​ Read​ Write​ Move​ Next State
q0​ 1​ 1​ R​ q0
q0​ +​ 1​ R​ q1
q1​ 1​ B​ S​ qaccept
Working:-
Input:
111+11
Tape:
111+11□
After replacing + with 1:
111111□
Delete one redundant symbol:
11111□
Machine enters:
qaccept
1. Define Turing Machine with 7-Tuple
A Turing Machine (TM) is an abstract computational model that consists of an infinite tape, a
read/write head, and a finite control unit.
M=(Q,Σ,Γ,δ,q0,B,F)=Q = Set of states,Σ = Input alphabet,Γ = Tape alphabet,δ = Transition
function,q₀ = Initial state,B = Blank symbol,F = Final states
2. Draw and Explain the Block Diagram of TM.
┌─────────────┐
│ Finite │
│ Control │
└──────┬──────┘
│
 ▼
----------------------------------
|a|a|b|b|□|□|□|
----------------------------------
▲
Read/Write Head
Components:
Infinite Tape
Read/Write Head
Finite Control
3. Explain Instantaneous Description (ID).
An Instantaneous Description represents the current configuration of a TM.
Current state
Tape contents
Head position
Example:
aq0bb
Current state = q0
[Link] Between DFA and Turing Machine
DFA​ ​ ​ Turing Machine
Read only​ ​ ​ Read & Write
Finite memory​ ​ ​ Infinite tape
Moves right only​ ​ Moves left & right
Accepts Regular Languages​ ​ Accepts Recursive Languages
5. What is a Universal Turing Machine (UTM)?
A Universal Turing Machine (UTM) is a Turing Machine that can simulate the behavior of any
other Turing Machine.
It takes as input:
.The description of a Turing Machine (M) .The input string (w)
and performs the same computation as machine M on input w.
Formal Representation
UTM(M, w)
Where:
M = Description of a Turing Machine
w = Input string
Working
Read the description of TM (M).
Read the input string (w).
Applications
Basis of modern digital computers.
7. Difference Between Recursive and RE Languages
Recursive Language​ ​ ​ ​ ​ Recursively Enumerable (RE) Language
TM always halts​ ​​ ​ ​ TM may not halt
Decidable language​ Semi-decidable language
Gives Accept or Reject for every input​ ​ ​ Accepts valid strings; may loop
forever for invalid strings
Every recursive language is RE​ ​ ​ ​ Not every RE language is recursive
Example:L={a^nb^n∣n≥1} Example:TM accepts valid strings, but for invalid
strings it may continue forever without halting.
8. What is a Multi-Tape Turing Machine?
A Multi-Tape TM contains:
Multiple tapes
Multiple read/write heads
One finite control
Advantages:
Faster computation
Easier algorithm design
9. What is a Recursive Language?
A Recursive Language is a language for which there exists a Turing Machine (TM) that always
halts and decides whether a given string belongs to the language or not.
Formal Definition
A language L is recursive if there exists a Turing Machine M such that:
M accepts every string in L.
M rejects every string not in L.
M halts for all inputs.
Example
L={a^nb^n∣n≥1}
Examples of strings in L:
ab
aabb
aaabbb
Properties
Recursive languages are decidable languages.
The Turing Machine always halts.
Every recursive language is also recursively enumerable.
[Link] Church–Turing Thesis
The Church–Turing Thesis states that:
Any problem that can be solved by an algorithm can be solved by a Turing Machine.
It was proposed independently by:
Alonzo Church
Alan Turing
Importance:
Forms the foundation of Computer Science.
Defines the concept of computability.
Helps determine whether a problem is computable or not.
Serves as the basis for modern computers and programming languages.
[Link] is Blank Symbol
A Blank Symbol is a special symbol used on the Turing Machine tape to represent an empty
cell.
It is usually denoted by:
B or □
Importance
Indicates unused tape positions.
Helps the TM identify the end of the input string.
Used while writing and erasing symbols on the tape.
Example
Input string:
aabb
Tape representation:
□ a a b b □ □ □ □ ...
Here, □ (Blank Symbol) represents empty tape cells.
In the 7-Tuple Representation
M=(Q,Σ,Γ,δ,q0,B,F)
where:
B = Blank Symbol
[Link] State in TM
A Halting State is a state in which the Turing Machine stops its computation and performs no
further actions.
The machine halts when it reaches either:
Accept State (qaccept) → Input is accepted.
Reject State (qreject) → Input is rejected.
Types of Halting States
Accept State
TM stops and accepts the input.
Reject State
TM stops and rejects the input.
Example:-
For input:aaabbb
If the string satisfies the language condition, TM enters:qaccept
and stops.
If the input is:aabbb
TM enters:qreject
and stops.
Diagram
q0 → q1 → q2 → qaccept
↘
qreject
Both qaccept and qreject are halting states.
[Link] is tape alphabet
The Tape Alphabet is the set of all symbols that can appear on the tape of a Turing Machine.
It is denoted by:
Γ(Gamma)
Properties
Contains all input symbols.
Contains the Blank Symbol (B or □).
May contain additional symbols used during computation (such as X, Y, Z).
Example
For a TM recognizing a^nb^n:
Σ = {a, b} (Input Alphabet)
Γ = {a, b, X, Y, B}
Where:
X = marked 'a'
Y = marked 'b'
B = blank symbol
Relation Between Σ and Γ
Σ⊆Γ
[Link] between PDA and TM
Pushdown Automata (PDA)​ Turing Machine (TM)
Uses a stack as memory.​ Uses an infinite tape as memory.
Can only push and pop symbols from stack.​ Can read, write, and modify tape symbols.
Recognizes Context-Free Languages (CFL).​ Recognizes Recursive and
Recursively Enumerable Languages.
Less powerful than TM.​ More powerful than PDA.
Input is read only once.​ Head can move left and right on tape.
Memory is limited by stack operations. ​ Memory is theoretically unlimited.
Ex:-PDA:L={a ^ n b ^ n ∣n≥1} ​ ​ ​ ​ Ex:TM:L={a^nb^nc^n∣n≥1}