[Nov_Dec_2022]

SPPU TE 🎖📚
SOLVED QUESTION PAPER
Theory of Computation
Q1)

a) Convert the following grammar to Chomsky Normal form (CNF) [9]

S→ a | aA | B
A→aBB | ε
B→ Aa | b
ANS
Original Grammar:
S → a | aA |
A → aBB | ε
B → Aa | b
Step 1 : Eliminate Null Production.
S→ a | aA | B | a
A → aBB | B | ε
B → Aa | a | b
Step 2 : Eliminate unit productions
S → a | aA | B | a
A → aBB | Aa | a | b | ε
B → Aa | a | b
Step 3: Replace terminals in productions by new terminal-producing non-terminals
S → X | YA | Z | X
A → YA | Xa | X | a | b | ε
B → Xa | X | b
X→a
Y→a
Z→b
Step 4: Convert remaining productions to binary productions
S → P | QA | R | P
A → QA | Pa | P | a | b | ε
B → Pa | P | b
P→a
Q→a
R→b

Now, the grammar is in Chomsky Normal Form (CNF).

b) Convert the following grammar to GNF. [9]

S→XB | AA
A→ a | SA
B→ b
X→ a

ANS
Original Grammar:
S→XB | AA
A→ a | SA
B→ b
X→ a
To convert to GNF, we need to eliminate ε-productions and make sure all productions are of the form
A→aα.

Step 1: The production rule A → SA is not in GNF, so we substitute S → XB | AA in the production rule
A → SA as:
S → XB | AA
A → a | XBA | AAA
B→b
X→a
Step 2: The production rule S → XB and B → XBA is not in GNF, so we substitute X → a in the production
rule S → XB and B → XBA as:
S → aB | AA
A → a | aBA | AAA
B→b
X→a
Step 3: Now we will remove left recursion (A → AAA), we get:
S → aB | AA
A → aC | aBAC
C → AAC | ε
B→b
X→a
Step 4: Now we will remove null production C → ε, we get:
S → aB | AA
A → aC | aBAC | a | aBA
C → AAC | AA
B→b
X→a
Step 5: The production rule S → AA is not in GNF, so we substitute A → aC | aBAC | a | aBA in
production rule S → AA as:
S → aB | aCA | aBACA | aA | aBAA
A → aC | aBAC | a | aBA
C → AAC
C → aCA | aBACA | aA | aBAA
B→b
X→a
Step 6: The production rule C → AAC is not in GNF, so we substitute A → aC | aBAC | a | aBA in
production rule C → AAC as:
S → aB | aCA | aBACA | aA | aBAA
A → aC | aBAC | a | aBA
C → aCAC | aBACAC | aAC | aBAAC
C → aCA | aBACA | aA | aBAA
B→b
X→a

Hence, this is the GNF form for the grammar G.

OR
Q2)

a) Show that the following grammar is ambiguous. [6]

S-> iCtS
S-> iCtSes
S-> a
C-> b
ANS
A grammar is ambiguous if there exists at least one string in the language generated by the grammar
that has more than one leftmost derivation or more than one parse tree.

Parse Tree 1 Parse Tree 2

As we can see, the string "ibtbes" has multiple leftmost derivations, which implies that the given grammar
Is ambiguous.

b) Convert the following grammar to chomsky normal form (CNF) [6]

G =({S}, {a, b}, P, S)
P= {S→aSa | bSb | a | b | aa | bb}
ANS
Since there are no ε-productions, unit productions and also all productions already have terminals and
non-terminals in the given grammar, we can move to the next step.

Step 1: Convert remaining productions to binary productions (productions with at most two symbols on
the right-hand side).
S → AS1 | BS2 | a | b | AS3 | BS4
S1 → a
S2 → b
S3 → a
S4 → b
Now, the productions satisfy the CNF requirements. The final CNF grammar is:
G = ({S, S1, S2, S3, S4}, {a, b}, P', S)
P' = {S → AS1 | BS2 | a | b | AS3 | BS4,
S1 → a
S2 → b,
S3 → a,
S4 → b}

c) Consider the following grammar. [6]

E-> E * E | E–E | id
Derive the string id-id*id using
i) Leftmost derivation
ii) Rightmost derivation

ANS
Given grammar
E → E * E | E - E | id
Leftmost Derivation Rightmost Derivation
E= E*E E=E–E
=E– E*E =E–E*E
= Id - E * E = E – E * id
= Id – id * E = E – id* id
=Id – id * id = id – id *id
Q3)

a) Find the transition rules of PDA for accepting a language [9]

L={w∈{a,b}* |w is of the a^n b^n with n≥ 1} through both empty stack and
final state and demonstrates the stack operation for the string aaabbb.

ANS A Pushdown Automaton (PDA) is a finite automaton with an additional stack memory.
The PDA for this language can be represented by the 7-tuple
(Q,Σ,Γ,δ,q0,Z,F).
Now, let's demonstrate the stack operation for the string "aaabbb":

(q_0, aaabbb, Z) -> (q_0, aabbb, XZ) // Push X onto the stack for 'a'
(q_0, aabbb, X) -> (q_0, abbb, XX) // Push X onto the stack for 'a'
(q_0, abbb, X) -> (q_0, bbb, X) // Pop X from the stack for 'b'
(q_1, bbb, \varepsilon) -> (q_1, bb, \varepsilon) // Pop X for 'b'
(q_1, bb, \varepsilon) -> (q_1, b, \varepsilon) // Pop X for 'b'
(q_1, b, \varepsilon) -> (q_1, \varepsilon, \varepsilon) // Pop X for 'b'
(q_f, \varepsilon, Z) // Accept as the stack is empty

Stack transition function:

(q0, a, z)
(q0, az)
(q0, a, a)
(q0, aa)
(q0, b, a)
(q1, \epsilon )
(q1, b, a)
(q1, \epsilon )
(q1, \epsilon, z)
(qf, z)

b) Design a PDA for accepting a language {a^n b^2n | n>=1} [9]

Simulate this PDA for the input string “aaabbbbbb”
ANS
So, the strings which are generated by the given language are as follows −
L={abb,aabbbb,aaabbbbbb,….}
Here a’s are followed by double the b’s

Whenever ‘a’ comes, push ‘a’ two times in the stack and if ‘a’ comes again then do the same.When ‘b’
comes then pop one ‘a’ from the stack each time. Note that b comes after ‘a’.
Finally at the end of the strings, if nothing is left in the STACK, then we can declare that language is
accepted in the PDA.
The PDA for the problem is as follows –

Transition functions
(q0, a, z)
(q1, az)
(q0, a, z)
(q3, aaz)
(q1, a, a)
(q1, aa)\
(q1, b, a)
(q2, \epsilon)
(q2, b, a)
(q2, \epsilon)
(q2, \epsilon, z)
(qf1, z)
(q3 a, a)
(q3, aaa)
(q3, b, a)
(q4, \epsilon)
(q4, b, a)
(q4, \epsilon)
(q4, \epsilon, z)
(qf2, z)

OR
Q4)

a) Design a PDA for accepting a language {0^n 1^m 0^n | m, n>=1}. [9]
Simulate this PDA for the input string “0011100”
ANS
In this PDA, n number of 0's are followed by any number of 1's followed n number of 0's. Hence the logic
for design of such PDA will be as follows:
Push all 0's onto the stack on encountering first 0's. Then if we read 1, just do nothing. Then read 0, and
on each read of 0, pop one 0 from the stack.

This scenario can be written in the ID form as:

δ(q0, 0, Z) = δ(q0, 0Z)
δ(q0, 0, 0) = δ(q0, 00)
δ(q0, 1, 0) = δ(q1, 0)
δ(q0, 1, 0) = δ(q1, 0)
δ(q1, 0, 0) = δ(q1, ε)
δ(q0, ε, Z) = δ(q2, Z) (ACCEPT state)

Now, let's simulate the PDA for the input string "0011100":

1. δ(q0, 0011100, Z) δ(q0, 011100, 0Z)

δ(q0, 11100, 00Z)
δ(q0, 1100, 00Z)
δ(q1, 100, 00Z)
δ(q1, 00, 00Z)
δ(q1, 0, 0Z)
δ(q1, ε, Z)
δ(q2, Z)
 b) Construct a PDA for L= {0^n 1^m 2^n 3^n | m,n≥ 0} [6]
ANS
Case 1 ; n=0
Case 1 ; m=0
Case 1 ; m,n>0
Case 1 ; m=0,n=0

Final Pushdown Automatan Can be;

(q0,0,z0) = (q0,z0)
(q0,0,0) = (q0,00)
(q0,1,0) = (q1,10)
(q0,1,1) = (q1,11)
(q0,2,1) =(q2, ε)
(q0,2,1) =( q2, ε)
(q0,3,0) = (q3, ε)
(q0,3,0) = (q3, ε)
(q0, ε,z0) =(q4,z0)
(q0,1,z0) =(q5,1z0)
(q0,1,1) =( q5,11)
(q0,2,1) =(q6, ε)
(q0,2,1) =( q6, ε)
(q0, ε,z0) =(q4,z0)
(q0,3,0) =( q3, ε)
(q0, ε,z0) =(q4,z0)
 C) Compare FA and PDA. [3]

ANS

Finite Automaton(FA) Pushdown Automaton(PDA)

(FA) is a used to recognize patterns within input (PDA) is a type of automata that employs a stack.
taken from some character set.

It doesn’t have the capability or space to store long It has the additional stack for storing long
sequence of input alphabets. sequence of alphabets.

Finite Automata can be constructed for Type-3 Pushdown Automata can be constructed for Type-
grammar 2 grammar.

constructed for regular language. constructed for context free grammar.

Q5)
a) Write a short note on Halting problem of Turing machine. [4]

ANS
The halting problem is a decision problem about properties of computer programs on a fixed Turing-
complete model of computation, i.e., all programs that can be written in some given programming
language that is general enough to be equivalent to a Turing machine.

Input - A Turing machine and an input string w.

Problem - Does the Turing machine finish computing of the string w in a finite number of steps? The
answer
must be either yes or no.
Proof -
At first, we will assume that such a Turing machine exists to solve this problem and then we will
show it is contradicting itself. We will call this Turing machine as a 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 –

Now we will design an inverted halting machine (HM)’ as –

 If H returns YES, then loop forever.

 If H returns NO, then halt.

The following is the block diagram of an ‘Inverted halting machine’ –

 Further, a machine (HM)2 which input itself is constructed as follows

 If (HM)2 halts on input, loop forever.

 Else, halt.

Here, we have got a contradiction. Hence, the halting problem is undecidable

b) Design a Turing Machine for the following language by Considering transition table and diagram.
i) TM That erases all non blank symbols on the tape where the sequence of non blank [9]
symbols does not contain any blank symbol B in between.
ii)TM that find 2’s complement of a binary machine. c) Design a Turing Machine that reads a
string representing a binary number and erases all leading 0’s in the string. However, if the
string comprises of only 0’s it keeps one 0.
ANS
i)
To design a Turing Machine (TM) for the specified language, we need to create a transition table and
diagram define how the machine behaves on different inputs.
a/B,R
a/B,R
qq
Q q1
q0
B/B,N
q2 is halt

Transition function is defined as:

(q0,a) = (q0,B,R)
(q0,b) = (q0,B,R)
(q1,b) = (q1,B,N)

ii)
Approach for 2's complement:
i. Scan input string from right to left
ii. Pass all consecutive '0's
iii. When '1' comes do nothing
iv. After that take complement of every digit.

2’s complement of a binary number is 1 added to the 1’s complement of the binary number.
 Transition Diagram:

Here, q0 shows the initial state and q1 and q2 shows the transition state and q3 shows the final state.
And 0, 1 are the variables used and R, L shows right and left.

b) Design a Turing Machine that reads a string representing a binary number and erases all leading
0’s in the string. However, if the string comprises of only 0’s it keeps one 0. [5]
ANS
Let us assume that the input string is terminated by a blank symbol, B, at each end of the string.
The Turing Machine, M, can be constructed by the following moves –
 Let q0 be the initial state.
 If M is in q0, on reading 0, it moves right, enters the state q1 and erases 0. On reading 1, it enters the
state q2 and moves right.
 If M is in q1, on reading 0, it moves right and erases 0, i.e., it replaces 0’s by B’s. On reaching the
leftmost 1, it enters q2 and moves right. If it reaches B, i.e., the string comprises of only 0’s, it moves
left and enters the state q3.
 If M is in q2, on reading either 0 or 1, it moves right. On reaching B, it moves left and enters the state
q4. This validates that the string comprises only of 0’s and 1’s.  If M is in q3, it replaces B by 0, moves
left and reaches the final state qf.
 If M is in q4, on reading either 0 or 1, it moves left. On reaching the beginning of the string, i.e., when
it reads B, it reaches the final state qf.

Hence,
M = {{q0, q1, q2, q3, q4, qf}, {0,1, B}, {1, B}, δ, q0, B, {qf}}
where δ is given by −
Tape alphabet Present Present Present Present Present
symbol State ‘q0’ State ‘q1’ State ‘q2’ State ‘q3’ State ‘q4’
0 BRq1 BRq1 ORq2 - OLq4
1 1Rq2 1Rq2 1Rq2 - 1Lq4
B BRq1 BLq3 BLq4 OLqf BRqf

OR
Q6)

a) Write short notes on: [4]

i) Reducibility
ii) Multi-tape Turing Machin

ANS
 Reducibility :

Reducibility is a fundamental concept in the theory of computation, particularly in the

context of Turing machines and decidability. When we say a problem A is reducible to problem B, it means that
solving problem B allows us to solve problem A. In other words, if there exists an algorithm to solve problem B,
we can use it to construct an algorithm to solve problem A. This concept is crucial for understanding the
relationships between different computational problems.
Reducibility is extensively used to classify problems into complexity classes and to prove
the inherent difficulty of certain problems. For example, many problems in computer science are classified as
NP-complete if they are as hard as the hardest problems in NP (nondeterministic polynomial time), and this
classification is based on polynomial-time reducibility.

 Multi-tape Turing Machin :

A multi-tape Turing machine is an extension of the classical Turing machine model that
incorporates multiple tapes, each with its own tape head. The machine operates on multiple tapes
simultaneously, and the transition function is defined based on the combination of symbols read from all tapes.
In a multi-tape Turing machine:

Configuration: The configuration of the machine is represented by the content of all tapes and the positions of
the tape heads.
Transition Function: The transition function specifies how the machine transitions between states based on
the symbols read from the current positions of all tape heads.
Computation: During a computation, each tape head moves independently, and the transition function dictates
the next state and the symbols to write on each tape.
The concept of multi-tape Turing machines contributes to the understanding of
computational complexity and the design of algorithms, providing insights into the efficiency of parallel
processing in the context of theoretical computation.

B) Construct a Turing Machine for R=aba*b [6]

ANS
Step 1: DFA FOR aba*b

a
a b b
q0 q1 q2 q3

Step 2 : DFA to TM
a/a,R
a/a,R b/b,R b/b,R q3
q0 q1 q2

B/B,N
q4
Halt
c)
Design a TM that multiplies two unary numbers over Σ={1}. [8]
Write simulation for the string 11*111

ANS
To design a Turing Machine (TM) that multiplies two unary numbers over the alphabet
Σ={1}, we need to create a machine that performs the multiplication operation for unary numbers.
Unary numbers are represented by sequences of '1's, and multiplication is essentially repeated addition.

1/1,R 1/1,R 1/1,L

1/1,R */*,R L/L,R B/B,L 1/1,L

q3 q4 q5
q0 q1 q2

*/1,N

q6

INPUT B 1 1 * 1 1 1 B
OUTPUT B 1 1 1 1 1 1 B

OR
Q7)

a) Justify “ Halting problem of Turing machine is undecidable” [8]

ANS
let's break down the statement "The halting problem of a Turing machine is undecidable" in simple
terms.

Now, why is it called undecidable? Imagine you have a magical machine (let's call it the Oracle) that
can answer any yes-or-no question about whether a given program will halt or not. We want to know
if this Oracle machine is possible to exist.
Here's a simple way to think about it:
o Assume we have this magical Oracle machine that can tell us whether any program halts or runs
forever.
o Now, let's create a new program (let's call it ParadoxProgram) that uses the Oracle machine to check
whether a modified version of itself will halt or run forever.
o If the Oracle machine says the modified version halts, then ParadoxProgram runs forever. If the Oracle
machine says it runs forever, then ParadoxProgram halts.
o This creates a paradox because no matter what the Oracle machine says, it leads to a contradiction.

Therefore, the initial assumption that we can have a magical Oracle machine that decides the halting
problem must be false. This means that there is no general algorithm (a step-by-step procedure) that can
determine whether any arbitrary program will halt or run forever. Hence, the halting problem for Turing
machines is undecidable.

In simpler terms, it's like saying there's no one-size-fits-all method to predict whether any computer program
will eventually finish or keep going forever. It's a fundamental limit in the world of computation.

b) Define and compare class P and class NP problem with suitable diagram [8]

ANS
P (POLYNOMIAL TIME):

Definition: The complexity class P is the set of all decision problems that can be solved with worst-case
polynomial time-complexity.

NP ((Nondeterministic Polynomial Time) :

Definition: It's a class of problems in computer science where, if you're given a potential solution, you can
quickly check if it's correct. However, finding the solution quickly (in polynomial time) is still an
open question for many problems in NP

P class Problem NP class Problem

P problems are a set of problems that can be NP problems are problems that can be solved in
solved in polynomial time by deterministic nondeterministic polynomial time.
algorithms.
P Problems can be solved and verified in The solution to NP problems cannot be obtained
polynomial time. in polynomial time, but if the solution is given, it
can be verified in polynomial time
P problems are a subset of NP problems. NP Problems are a superset of P problem

All P problems are deterministic in nature. All the NP problems are non-deterministic in
nature
The solution to P class problems is easy to find The solution to NP class problems is hard to find

Examples of P problems are: Selection sort, Examples of NP problems are the Travelling
Linear Search salesman problem and the knapsack problem.

OR
Q8)

a) Explain in brief the term “recursively enumerable”. [6]

ANS
The term "recursively enumerable" is related to the concept of computability in theoretical computer
science.

A set of natural numbers is said to be recursively enumerable if there exists an algorithm (a procedure
or a computer program) that can enumerate its elements one by one. In other words, a set is recursively
enumerable if there is a method to generate its members through an effective procedure.

Formally, a set A is recursively enumerable if there exists a partial recursive function (a computable
function) whose domain is exactly the set A. This means that there is a Turing machine (or an equivalent
computational model) that, when given an input, either halts and outputs 1 if the input belongs to A or
does not halt (runs forever) if the input does not belong to A.

The concept of recursively enumerable sets is closely related to the broader notion of decidability. If a
set is both recursively enumerable and its complement is recursively enumerable, then the set is said to
be decidable.

In summary, a recursively enumerable set is one for which there exists a procedure to generate its
members, even if the procedure might not terminate for inputs not in the set.

b) Explain examples of problems in NP. [6]

ANS
Certainly! Problems in NP (Nondeterministic Polynomial time) are characterized by the property that,
given a solution, you can efficiently check whether it's correct. However, finding a solution efficiently is an open
question for many of these problems. Here are a few examples:

1) SAT (Boolean Satisfiability Problem):

 Given a Boolean formula, is there an assignment of truth values to the variables that makes the
formula true?

2) 3SAT (3-Satisfiability Problem):

 Similar to SAT, but with the restriction that each clause in the Boolean formula must have exactly three
literals (variables or their negations).

3) Vertex Cover:
 Given an undirected graph, is there a set of vertices such that every edge in the graph is incident to at
least one vertex in the set?

4) Subset Sum:
 Given a set of integers and a target sum, is there a subset of the integers that adds up to the target sum?

5) Traveling Salesman Problem (TSP):

 Given a list of cities and the distances between each pair of cities, is there a tour that visits each city
exactly once and returns to the starting city with the minimum total distance?

6) Knapsack Problem:
 Given a set of items, each with a weight and a value, determine the maximum value that can be obtained
by selecting a subset of the items with a total weight not exceeding a given limit.

7) Hamiltonian Cycle:
 Given a graph, is there a cycle that visits every vertex exactly once?
 8) Clique Problem:
 Given an undirected graph, is there a subset of vertices such that every pair of distinct vertices in the
subset is connected by an edge?

9) Integer Factorization:
 Given a composite integer, can it be expressed as a product of two non-trivial integers? (This problem is
not known to be in P, but efficient algorithms for it would have significant implications for
cryptography.)

10) Graph Isomorphism:

 Given two graphs, do they have the same structure (are they isomorphic)?

These problems are considered to be in NP because, if someone provides a solution, it can be verified quickly.
However, whether there exist efficient algorithms to find these solutions (i.e., whether P equals NP) is an open
question in computer science.

c) Differentiate between P Class and NP class. [4]

ANS

P class Problem NP class Problem

P problems are a set of problems that can be NP problems are problems that can be solved in
solved in polynomial time by deterministic nondeterministic polynomial time.
algorithms.
P Problems can be solved and verified in The solution to NP problems cannot be obtained
polynomial time. in polynomial time, but if the solution is given, it
can be verified in polynomial time
P problems are a subset of NP problems. NP Problems are a superset of P problem

All P problems are deterministic in nature. All the NP problems are non-deterministic in
nature
The solution to P class problems is easy to find The solution to NP class problems is hard to find

Examples of P problems are: Selection sort, Examples of NP problems are the Travelling
Linear Search salesman problem and the knapsack problem.