CS8501- Theory of Computations Department of CSE 2020-2021

Course Outcomes (COs)

C304.1 : Able to design automata for any given pattern
: Able to design automata for any given pattern and find its equivalent regular
C304.2
expressions
C304.3 : Able to design a context free grammar for any given language
C304.4 : Able to understand Turing machines and their capability
C304.5 : Able to understand undecidable problems and NP class problems

MAPPING BETWEEN COs, POs AND PSOs

COs PROGRAMME OUTCOMES (POs) PSOs

PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12 PSO1 PSO2 PSO3

C304.1 3 3 3 - - - - - - - - - 3 1 -

C304.2 3 3 3 - - - - - - - - - 3 1 -

C304.3 3 3 3 - - - - - - - - - 3 1 -

C304.4 3 3 3 - - - - - - - - - 3 1 -

C304.5 3 3 3 - - - - - - - - - 2 - 1

RELATION BETWEEN COURSE CONTENTS WITH COs

S. No Knowledge Level Contents COs

UNIT I AUTOMATA FUNDAMENTALS
Introduction to formal proof
 Understanding
 Additional forms of Proof
1  Inductive Proofs C304.1
 Analyzing
 Deductive Proofs
 Structural Induction
Introduction to Finite Automata
 Understanding
 Formal Definition
2  Finite Automata Model C304.1
 Applying
 Need of Automata
 Types of Finite Automata
Deterministic Finite Automata
 Notations
 Understanding  Formal Definition
3 C304.1
 Applying  Transition Diagram and Table of DFA
 Transition Function of DFA
 Example Problems on DFA
Non Deterministic Finite Automata
 Notations
 Understanding
 Formal Definition
4  Transition Diagram and Table of NFA C304.1
 Applying
 Transition Function of NFA
 Comparison of NFA and DFA
 Example Problems on NFA
St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 1 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
Finite Automata with Epsilon Transitions
 Formal Definition NFA with Epsilon Transition
 Understanding  Epsilon – Closure Definition
5 C304.1
 Applying  Transition Diagram and Table of Epsilon NFA
 Transition Function of Epsilon NFA
 Problem on Epsilon NFA
UNIT II REGULAR EXPRESSIONS AND LANGUAGES
Regular Expressions
 Understanding  Formal Definition
1 C304.2
 Applying  Operations of Regular Expressions
 Example Problems
 Understanding FA and Regular Expressions(RE)
2 C304.2
 Applying  Regular Language
 Understanding Proving Languages not to be regular
3  Theorem C304.2
 Analyzing
 Problem Related to Pumping Lemma
 Understanding Closure Properties of Regular Languages
4  Theorem C304.2
 Analyzing
 Advantages of Pumping lemma
Equivalence and Minimization of Automata
 Understanding  Equivalence of NFA and RE
5  Conversion of RE to DFA C304.2
 Analyzing
 Conversion of Finite Automata to RE
 Minimization of DFA
UNIT III CONTEXT FREE GRAMMAR AND LANGUAGES

 Understanding Context Free Grammars(CFG)

1  Languages of Context Free Grammar C304.3
 Analyzing
 Design of Context Free Grammar
 Understanding Parse Trees
2  Construction of Parse Tree C304.3
 Applying
 Examples on Parse Tree
Ambiguity in Grammars and Languages
 Understanding  Derivation Tree
3  Ambiguity C304.3
 Applying
 Example on Ambiguity in Grammars and
Languages
Introduction to Pushdown Automata
 Understanding  Formal Definition of PDA
 Components of PDA C304.3
 Applying
 Description & move of PDA
 Instantaneous Description of PDA
 Understanding Design of PDA
 Designing a PDA for the given Language C304.3
 Applying
 Example Problems on PDA
Languages Accepted by PDA
 Understanding  Accepted by Final State
C304.3
 Applying  Accepted by Empty Stack
 Problems
Types of PDA
 Understanding  Deterministic PDA
4 C304.3
 Applying  Non Deterministic PDA
 Problems

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 2 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
 Understanding Equivalence of Pushdown automata and CFG
5  Conversion from Context Free Grammar to PDA C304.3
 Applying
 Construction of CFG for a given PDA
 Understanding Deterministic Push Down Automata(DPDA)
6 C304.3
 Applying  Example Problems on DPDA
UNIT IV PROPERTIES OF CONTEXT FREE LANGUAGES
Normal Forms for CFG
 Understanding  Greiback Normal form (GNF)
1  Chomsky normal form(CNF) C304.4
 Analyzing
 Problems related to CNF and GNF

 Understanding Pumping Lemma for CFL

2  Problem Based on Pumping Lemma C304.4
 Analyzing
 Understanding Closure Properties of CFL
3 C304.4
 Applying
Introduction to Turing Machine
 Understanding  Formal Definition of TM
4  Components of TM C304.4
 Applying
 Description & moves of TM
 Instantaneous Description of TM
 Understanding Design of TM
5  Designing a TM for the given Language C304.4
 Applying
 Problems
Techniques for Turing Machine construction
 Storage in the finite control
 Understanding  Multiple Tracks
6 C304.4
 Analyzing  Checking off symbols
 Shifting over
 Subroutines
UNIT V UNDECIDABILITY
Non Recursive Enumerable (RE) Language
 Understanding  Recursively Enumerable (RE) Languages
1  Diogonalization Language C304.5
 Analyzing
 Enumerating a Language
 Decidable Problem
 Understanding Undecidable Problem with RE
2  Halting Problem C304.5
 Applying
 Rice Theorem
 Understanding Undecidable Problems about TM
3  Example problems C304.5
 Analyzing
 Understanding
4 Post‘s Correspondence Problem C304.5
 Applying
 Understanding P and NP completeness
5 C304.5
 Applying  Class P & Class NP
Topics beyond the Syllabus
 Understanding Reading a stream of tokens and builds a syntax tree by C304.1,
1  Analyzing calling the appropriate constructor function for C304.2,
 Applying Intermediate Code Generation C304.4

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 3 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
Prerequisite: Semester IV CS8541 – Design & Analysis of Algorithm

CS8501 – Theory of
Computations

Introduction
Automata
to Finite Regular
DataExpressions
Analysis And MiningFree
Context DataGrammar
Streams Properties Of Context Free Undecidability
Fundamentals
Automata Languages And Languages Languages

Context Free Normal Forms

Introduction to Regular
Regression Stream Computing
Ambiguity in Hadoop
Non Recursive
Grammar Grammar & Language for CFG
formal proof Expressions
Modeling Enumerable (RE)
Analysis
Operationofon Language
time
Regular
Series
Exp
Parse Definition of CNF & GNF
Additional forms Multivariate
FA and Trees the Pushdown Undecidable
Design of FA
of Proof Regular
Analysis Closure Automata Problem with RE
Expressions Properties of
Regular
Inductive Derivations Deterministic Apriori
Languages Design of TM
Proofs PDA Algorithm
Proving Halting
Languages not
Problem
to be regular

Soft Computing
Equivalence of FA Programming
Languages of a Techniques for TM.
Finite Automata Rice Theorem
Pushdown
Automata
Minimization
Rule of FA
Induction Pumping Lemma
Operations onFA
Deterministic RE
Equivalence of for CFL Undecidable
Equivalence of
Counting Automata
Pushdown Oneness functions Problems about
NFA & DFA
and CFG TM
Non Deterministic
Closure Properties of
FA
CFL
NFA to Post„s
DFA Correspondence
Epsilon NFA Problem

RE to DFA The Class P

Properties of Epsilon The Class NP

NFA

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 4 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
UNIT I AUTOMATA FUNDAMENTALS
Introduction to formal proof – Additional form of proof – Inductive proofs - Finite
Automata – Deterministic Finite Automata – Non Deterministic Finite Automata - Finite
Automata with Epsilon Transitions.
UNIT-I / PART-A
1. Define computation and theory of computation.
Computation can be defined as finding a solution to a problem from the given
inputs by means of an algorithm. The theory of computation, a subfield of computer
science and mathematics, deals with finding solutions to problems from the given
inputs.
2. What is finite automaton or finite state machine (FSM)? (Dec 15) (Dec 17)
A finite state machine or finite automaton is a machine, or a mathematical model
of a machine, which can only reach a finite number of states and transitions. It is used
in mathematical problem analysis. Or A general model of a machine is called a finite
automaton. Finite because the number of states and the alphabet of input symbols is
finite: automaton because the structure or the machine is deterministic, i.e., the change
of state is completely governed by the input.
3. What is deductive proof?
A deductive proof consists of a sequence of statements, which starts from a hypothesis,
or a given statement to a conclusion. Each step is satisfying some logical principle.
4. Define Induction principle.
Basis step:
 P(1) is true.
 Assume p(k) is true.
 P(K+1) is shown to be true.
5. Define symbol, alphabet and string.
 A symbol is a single object and is an abstract entity that has no meaning by
itself. Example alpha
 An alphabet is any finite, non-empty set of symbols/characters. It is denoted by
. Example:  ={0,1} is a binary alphabet, consisting symbols of 0 and 1
 A string is a finite sequence of symbols chosen from some alphabet. Example if
 = {0, 1} then 01010, 111, 11,00,01,10 are some of the strings chosen from this
alphabet.
6. Define Deterministic finite automata (DFA). (Dec 16)
Formally a DFA consists of 5-tuples M = (Q,,,q0, F),Where
Q - Finite set of states
 - Finite set of input symbols called alphabet
qo - Initial state (q0 Є Q)
F - Set of accepting states or final states (F is subset of Q)
 - Transition function defined as  : Q → Q

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 5 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
7. Define proof by contrapositive.
It is other form of if then statement. The contra positive of the statement “if H
then C” is “if not C then not H”.
8. How can you represent the transitions of DFA?
The transitions of DFA can be represented using
 Transition diagram: If (p,a) = q then the arrow goes from the vertex which
corresponds to state p, to the vertex that corresponds to state q labeled a.
 Transition table: Rows corresponds to states and columns correspond to inputs.
An entry corresponds to next states to indicate the transition of DFA.
9. Define extended transition function for a DFA.
 For DFA, M = (Q,,,q0, F),the transition function  is extended as δ: Q∑* Q
and is defined as follows.
 For any state q of Q δ(q, ε ) = q (This means that DFA stays in the same state q
when it reads an empty string at q)
 For any state q of Q, any string x∑* with „a‟ as the last symbol of x and a∑ ,
then δ(q, xa)= δ( δ(q, x),a)
10. Define the languages accepted by DFA
The language accepted by DFA M = (Q,,, q0, F) is the set of strings ∑ accepted
by M i.e., L(M) = { w∑* / δ(q0,w) is in F}. The language is said to be rejected by DFA
M = (Q, , , q0, F) such that L(M) = { w∑* / δ(q0,w) is not in F}.
11. Define Epsilon transition.
Transitions that take place without reading any input symbols are called Epsilon
transition (Є – transition).
12. Define - closure of a state.
- closure of a given state „q‟ is defined as the set of all states ,that can be reached from q
on a path labeled by .
13. What is optimum DFA?
Minimization or optimization of a DFA refers to the detection of those states of DFA,
whose presence or absence in a DFA does not affect the language accepted by the
automata.
14. Draw deterministic automata to accept strings containing the substring 0101.

15. Draw non-deterministic automata to accept strings containing the substring 0101.
(May 16)

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 6 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
16. Define Non-deterministic finite automata (NFA or NDFA). (Dec 2019)
Formally a NFA consists of 5-tuples M = (Q,,,q0, F),Where
Q - Finite set of states
 - Finite set of input symbols called alphabet
qo - Initial state (q0 Є Q)
F - Set of accepting states or final states (F is subset of Q)
 - Transition function defined as  : Q → 2Q or P(Q) where
P(Q) denotes the power set of Q
17. Define extended transition function for a NFA.
For NFA, M = (Q,,,q0, F),the transition function  is extended as δ: Q∑* P(Q) and is
defined as follows.
 For any state q of Q δ(q, ε ) = {q} (This means that DFA stays in the same state q
when it reads an empty string at q)
 For any state q of Q, any string x∑* with „a‟ as the last symbol of x and a∑ ,
then δ(q, xa)= Ṳ for every p in q δ(p, a) or δ(q, xa) = Ṳ pδ(q, x) δ(p,a)
18. How a Non deterministic finite state automaton (NFA) differs from a Deterministic
DFA NFA
On each input there is one and only one On each input the automaton can be in
state to which the automaton on move several states at once
from its current state
The transition function returns only one The transition function returns zero, one or
state.(i.e) more states. (i.e)
Construction of DFA is difficult compared Construction of NFA is easy compared to
to NFA (Take more space) DFA. (Takes less space)
Implementation of DFA is easy compared Implementation of NFA is difficult
to NFA. (speeds up computation) compared to DFA. (slow computation
process)
19. Define Non-deterministic finite automata with Є moves (NFA or NDFA).
Formally a NFA with Є moves consists of 5-tuples M = (Q,,,q0, F),Where
Q - Finite set of states
 - Finite set of input symbols called alphabet
qo - Initial state (q0 Є Q)
F - Set of accepting states or final states (F is subset of Q)
 - Transition function defined as  : Q( ṲЄ) → 2Q or P(Q)
where P(Q) denotes the power set of Q
20. Construct an NFA with Є-moves to accept all the strings with any number of a’s
followed by any number of b’s followed by any number of c’s.
Transition table
Q a b c Є
qo { qo} ø ø {q1}
q1 ø {q1} ø {q2}
q2 ø ø {q2} ø

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 7 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
21. Generate NFA with Epsilon to represent a*b/c (May 17)
First draw a* (Kleene closure)
Then draw for a*b (Concatenation)
Finally draw for a*b/c (Union)
22.
Find and prove by induction a formula for (Dec 2019)

UNIT-I / PART-B
1. Use mathematical induction to prove that 1 + 2 + 3 + ... + n = n (n + 1) / 2 for all
positive integers n.
2. Prove that 1 2 + 2 2 + 3 2 + ... + n 2 = n (n + 1) (2n + 1)/ 6 For all positive integers n.
3. Use mathematical induction to prove that 1 3 + 2 3 + 3 3 + ... + n 3 = n 2 (n + 1) 2 / 4 for all
positive integers n.
4. Prove that for any positive integer number n , n 3 + 2 n is divisible by 3
5. Construct a DFA that accepts all strings on {0,1} except those containing the substring
101.
6. Construct NFA with Epsilon for the RE = (a/b)*ab
7. Given ∑= {a,b}, construct a DFA which recognize the language L = {bm a bn: m, n > 0}
(Dec 16)
8. If L is accepted by an NFA with ϵ–transitions, then L is accepted by an NFA without ϵ–
transitions.
9. Prove for every n>=1 by mathematical induction Σ i2 = {n (n+1)/2}2. (May 17)

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 8 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
10. Give non Deterministic finite automata accepting the set of strings in (0+1)* such that
two 0’s are separated by a string whose length is 4i, for some i>=0. (Dec 19)

11. Construct DFA equivalent NFA {{P,Q,R,S},{0,1}, , P,{S}} Where is defined as

(Dec 19)
0 1
p p,q p
q r r
r s -
s s s
UNIT II REGULAR EXPRESSIONS AND LANGUAGES
Regular Expressions – FA and Regular Expressions – Proving Languages not to be regular –
Closure Properties of Regular Languages – Equivalence and Minimization of Automata.
UNIT-II / PART-A
1. What is a regular expression?
A regular expression is a string that describes the whole set of strings according to
certain syntax rules. These expressions are used by many text editors and utilities to
search bodies of text for certain patterns etc. Definition is: Let Σ be an alphabet. The
regular expression over Σ and the sets they denote are:
i. Φ is a r.e and denotes empty set. ii. Є is a r.e and denotes the set {Є}
iii. For each „a‟ in Σ , a+ is a r.e and denotes the set {a}.
iv. If „r‟ and „s‟ are r.e denoting the languages R and S respectively then (r+s),
(rs) and (r*) are r.e that denote the sets RUS, RS and R* respectively.
2. Write regular expression for the set of strings over {0,1} that have atleast one and
atmost one. (Dec 15)
0* 1 (0 | 1)*
0* | 0* 1 0*
3. State the Pumping lemma for regular languages. (May 16) (Dec 17)(Dec 19)
Let L be a regular language, accepted by some finite automaton D with a string w in
L written as w=xyz, then
 |xv |≤ n,
 |y| ≥ 1 then
 xyiz  L for all i ≥ 0.
4. Construct a r.e for the language which accepts all strings with atleast two c’s over the
set Σ={c,b}.
(b+c)* c (b+c)* c (b+c)*

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 9 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
5. What are the closure properties of regular languages? (Dec 16) (Dec 17)
Regular languages are closed under a wide variety of operations.
 Union
 intersection
 Set complement
 String reversal
 Set difference
 Concatenation
 Star
 Homomorphism
6. Give language of regular expression a?(b/c)* (May 17)
a? means either a or ε
(b/c)* means the set of all symbols no other than b and c including the empty string = {ε,
b, c, bb, cc, cb, bc, bbb, ccc,…}
7. Show whether a language L= {0n12n | n>0} is regular or not using pumping lemma.
(May 17)
To prove that L is not a regular language, we will use a proof by contradiction. Assume
that L is regular.
Let L be a regular language, accepted by some finite automaton D with a string w in
L written as w=xyz, then
|xv |≤ n,
|y| ≥ 1 then
xyiz  L for all i ≥ 0.
But, this is clearly not in L.This is a contradiction with the pumping lemma. Therefore
our assumption that L is regular is incorrect, and L is not a regular language
8. Differentiate L* and L+
L* denotes Kleene closure and is given by L* =U Li
i=0
example : 0* ={Є ,0,00,000,…………………………………}
Language includes empty words also.
L+ denotes Positive closure and is given by L+= U Li
i=1 example:0+={0,00,000,……………………………………..}
9. What is Arden’s Theorem?
Arden‟s theorem helps in checking the equivalence of two regular expressions. Let P
and Q be the two regular expressions over the input alphabet Σ. The regular
expression R is given as : R=Q+RP
Which has a unique solution as R=QP*.
10. Reg exp denoting a language over Σ ={1} having
(i)even length of string (ii)odd length of a string.
(i) Even length of string RE=(11)*
(ii) Odd length of the string RE=1(11)*

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 10 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
11. Write a r.e to denote a language L which accepts all the strings which begin or end
with either 00 or 11.
The r.e consists of two parts: L1=(00+11) (any no of 0‟s and 1‟s)
=(00+11)(0+1)*
L2=(any no of 0‟s and 1‟s)(00+11)
=(0+1)*(00+11) Hence r.e R=L1+L2
=[(00+11)(0+1)*] + [(0+1)* (00+11)]
12. Construct a r.e for the language over the set Σ={a,b} in which total number of a’s are
divisible by 3
( b* a b* a b* a b*)*
13. what is: (i) (0+1)* (ii)(01)* (iii)(0+1) (iv)(0+1)+
(0+1)*= { Є , 0 , 1 , 01 , 10 ,001 ,101 ,101001,…………………}
Any combinations of 0‟s and 1‟s.
(01)*={Є , 01 ,0101 ,010101 ,…………………………………..}
All combinations with the pattern 01. (0+1)= 0 or 1,No other possibilities.
(0+1)+= {0,1,01,10,1000,0101,………………………………….}
14. Reg exp for:
(i)All strings over {0,1} with the substring ‘0101’
(ii)All strings beginning with ’11 ‘ and ending with ‘ab’
(iii)Set of all strings over {a,b}with 3 consecutive b’s.
(iv)Set of all strings that end with ‘1’and has no substring ‘00’
(i)(0+1)* 0101(0+1)* (ii)11(1+a+b)* ab
(iii)(a+b)* bbb (a+b)* (iv)(1+01)* (10+11)* 1
15. What are the applications of Regular expressions and Finite automata
Lexical analyzers and Text editors are two applications.
Lexical analyzers:The tokens of the programming language can be expressed
using regular expressions. The lexical analyzer scans the input program and separates
the tokens.For eg identifier can be expressed as a regular expression as:
(letter)(letter+digit)*
If anything in the source language matches with this reg exp then it is recognized as an
identifier.The letter is{A,B,C,………..Z,a,b,c….z} and digit is
{0,1,…9}.Thus reg exp identifies token in a language.
Text editors: These are programs used for processing the text. For example
UNIX text editors uses the reg exp for substituting the strings such as: S/bbb*/b/
Gives the substitute a single blank for the first string of two or more blanks in a given
line. In UNIX text editors any reg exp is converted to an NFA with Є –transitions, this
NFA can be then simulated directly.
16. Reg exp for the language that accepts all strings in which ‘a’ appears tripled over the
set Σ ={a}
RE=(aaa)*

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 11 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
17. What are the applications of pumping lemma?
Pumping lemma is used to check if a language is regular or not.
(i) Assume that the language(L) is regular.
(ii) Select a constant „n‟.
(iii) Select a string(z) in L, such that |z|>n.
(iv) Split the word z into u,v and w such that |uv|<=n and |v|>=1.
(v) You achieve a contradiction to pumping lemma that there exists an „i‟
Such that uviw is not in L.Then L is not a regular language.
18. What is the closure property of regular sets?
The regular sets are closed under union, concatenation and Kleene closure.
r1Ur2= r1 +r2
r1.r2= r1r2 ( r )*=r*
The class of regular sets are closed under complementation, substitution,
homomorphism and inverse homomorphism.
19. Reg exp for the language such that every string will have atleast one ‘a’ followed by
atleast one ‘b’.
RE=a+b+
20. Write the exp for the language starting with and has no consecutive b’s
RE=(a+ab)*
21. Construct the expression corresponding to the state diagram (Dec 2019)

Let us form the equations

q1 = q10 + q30 + є
q2 = q11 + q21 + q31
q3 = q20
Solving the equations
q2 = q11 + q21 + (q20)1 = q11 + q2(1 + 01)
q2 = q11 (1 + 01)*
So, q1 = q10 + q30 + є
q1= q10 + q11(1 + 01*)00 + є
= q1(0 + 1(1 + 01)*00) + є
= є (0 + 1(1 + 01)*00)*
q1=(0 + 1(1 + 01)*00)*
So the regular expression for the given automata is =(0 + 1(1 + 01)*00)*
UNIT-II / PART-B
1. Let L be a set accepted by a NFA and then prove that there exists a DFA that accepts L.
(Dec 15)
2. Construct a NFA that accepts all strings that end in 01.Give its transition table and
extended transition function for the input string 00101.Also construct a DFA for the
above NFA using subset construction method. (May 16)

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 12 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
3. What is regular expression? Write a regular expression for the set strings that consists of
alternating 0‟s and 1‟s. (May 16)
4. Discuss the basic approach to convert from NFA to regular expression. Illustrate with
an example. (Dec 16)
5. Construct the DFA equivalent to the NFA. M = {{a, b, c, d} {0, 1}, δ, a, {b, d}} where δ is
defined as
δ 0 1
a {b,d} {b}
b c { b,c}
c d a
d - a
6. (a) Construct a minimized DFA for the RE 10 + (0 + 11) 0*1.
(b) Let r be a regular Expression. Then prove that there exists an NFA withϵ –
transitions that accept L(r).
7. Write and explain the algorithm for minimization of a DFA. Using the above algorithm
minimize the following DFA. (May 16)
States 0 1
A B F
B G C
C A C
D C G
E H F
F C G
G G E
H G C
8. Consider the following NFA for an identifier. Consider the closure of each state and
finit‟s equivalent DFA. (Dec 15)

9. Determine the DFA from the given NFA. M = ({q0,q1}, {a,b}, δ, q0, {q1}) with the state
diagram table δ given below. (Dec 16)
δ a ba
q0 {q0,q1} {q1}
q1 ϕ {q0,q1}
10. a) State the pumping lemma for regular languages. Prove that L = {0i2/ i is an integer; i
≥1} is not regular. (Dec 15)
b) Show that the language L= {anbn:n≥0} is not regular.

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 13 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
11. Convert the Epsilon-NFA to DFA and list the difference between NFA and DFA (Dec
17)
States a b ε
q0 q1
q1 q1 q2
q2 q0
12. Show that the regular language are closed under: (Dec 17)
i) Union
ii) Intersection
iii) Kleene closure
iv) Complement
v) Difference
13. Construct NFA with Epsilon for the RE = (a/b)*ab and convert into DFA and further
find the minimized DFA. (May 17)
14. Construct finite automata equivalent to the regular expression (ab+a)* (Dec 15)
15. (i) Prove that any language accepted by DFA can be represented by a regular
expression.
(ii) Construct finite automata for the regular expression. 10+(0+11)0*1 (Dec 19)
16. Set of strings of 0‟s and 1‟s , beginning with a 1, whose value treated as a binary number
is a prime. (Dec 19)
UNIT III CONTEXT FREE GRAMMAR AND LANGUAGES
CFG – Parse Trees – Ambiguity in Grammars and Languages – Definition of the Pushdown
Automata – Languages of Pushdown Automata – Equivalence of Pushdown Automata and
CFG, Deterministic Pushdown Automata.
PART-A
1. Define Context Free Grammar (CFG). (Dec 16)
A CFG, G is formally defined as a 4-tuple G = (V, T, P,S) where
V Finite set of Variables or non-terminals
T Finite set of Terminals
P Finite set of Production rule
S Start symbol, SЄV
2. What do you mean by language of a CFG?
The language generated (defined, derived, produced) by a CFG, is the set of all strings
of terminals, that can be produced from the start symbol S using the productions as
substitutions. A language generated by CFG is called context-free language (CFL) and
is denoted by L (G).
3. Construct the CFG representing the palindrome over (0+1)* (Dec 15)
Let the CFG, G = (V, T, P, S) where, S is the start symbol
V = {S}
T = {0, 1}
P = { S→0|1| Є
S→0S0
S→1S1 }

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 14 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
4. Construct a CFG for set of strings that contain equal number of a’s and b’s over
∑={a,b} (May 16)
Let the CFG, G = (V, T, P, S) where, S is the start symbol
V = {S}
T = {a,b}
P = { S→ Є
S→aSb
S→bSa
S→SS
}
5. Construct a CFG to generate the language L= {anb2n/ n≥1}
Let the CFG, G = (V, T, P, S) where, S is the start symbol
V = {S}
T = {a,b}
P={
S→aSbb
S→abb
}
6. Derive a string ’aababa’ for the following context free grammar (CFG) (Dec 17)
S→aSX/b
X→Xb/a
S => aSX
=> aaSXX
=>aabXX
=> aabXbX
=> aababX
=> aababa
7. Generate CFG for a signed integer constant in C language (May 17)
Integer can begin with + or - and after that we have non-empty string of digits.
Integer must not contain unnecessary leading zeros and zero should not be preceded by
+ or -. For example: 0; 123; -15; +9999 are correct, but +0; 01; +-3; +09; + are incorrect.
(number) ::= 0 | (nonzero unsigned number) | (sign)(nonzero unsigned number)
(sign) ::= + | -
(nonzero unsigned number) ::= (nonzero digit)(digits)
(nonzero digit) ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
(digit) ::= 0 | (nonzero digit)
(digits) ::= | (digits)(digit)

8. What do you mean by useful symbol in CFG?

A grammar symbol X in CFG is useful, iff
 it derives a string of terminals
 it is used in derivation at least one w in L.
9. What is CFL?
L is a context free language (CFL) if it is L(G) for some CFG G. The language generated
by G ( L(G) ) is {w | w is in T* and S =>w .

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 15 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
10. If S->aSb | aAb , A->bAa , A->ba .Find out the CFL.
S->aAb=>abab
S->aSb=>a aAb b =>a a ba b b(sub S->aAb) S->aSb =>a aSb b =>a a aAb b b=>a a a ba b
bb
Thus L={anbmambn, where n,m>=1}
11. What are the properties of the CFL generated by a CFG?
Each variable and each terminal of G appears in the derivation of some word in L
There are no productions of the form A->B where A and B are variables.
12. Find L(G) where G= ( {S} ,{0,1}, {S->0S1 ,S->Є },S )
S->Є , Є is in L(G)
S-> 0S1 =>0Є1=>01
S->0S1=>0 0S11=>0011
Thus L(G)= { 0n1n | n>=0}
13. Give the steps to eliminate useless symbols. (Dec 17)
 Step 1: Find the variables which can be derived from the terminal string.
(Directly or indirectly)
 Step 2: Find the variables which are reachable from the start state.
14. What is CFL?
L is a context free language (CFL) if it is L(G) for some CFG G. The language generated
by G ( L(G) ) is {w | w is in T* and S =>w .
15. What do you mean by null production and unit production? Give an example. (May 16)
A production of the form A→Є is called null production. Example: S→0|1| Є.
Any production of the form A→B whose RHS contains single variable is called unit
production. Example: B → C | b, C→D
16. What is parse tree?
When deriving a string w from S, if every derivation is considered to be a step in
the tree construction, then the graphical display of the derivation of string w results in a
tree structure. This is called a derivation tree or parses tree or generation tree or
production tree.
17. What do you mean by production?
Production refers to the set of rules used to construct the valid sentences from the given
grammar.
18. What do you mean by derivations?
The sequence of substitutions, used to obtain a string is called a derivation.
Derivation refers to replacing an instance of a given string‟s non-terminal, by the RHS of
the production rule, whose LHS contains the non-terminals to be replaced.
19. What do you mean by non-terminals and terminals?
The symbols that may be replaced by other symbols are called non-terminals or
variables. Non-terminals typically are upper case letters. The symbols that cannot be
replaced by other symbols are called terminals. Terminals typically are lower case
letters.

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 16 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
20. What are the various forms of production?
 Unit production: Any production of the form A→B is a unit production
 Є-production: Any production of the form A→Є is called Є-production
 Recursive production: A production is called recursive if its LHS occurs on its
RHS or non-terminals are present on both sides of →. Example: S→aS
 Indirectly recursive production: A production which is not directly recursive is
an indirectly recursive production. Example S→b| a A A→b S
21. What are the two types of derivations?
 Left most derivation (LMD): A derivation is said to be leftmost if in each step,
the leftmost variable in the sentential form is replaced.
 Right most derivation (RMD): A derivation is said to be rightmost if in each
step, the rightmost variable in the sentential form is replaced.
22. Construct a rightmost derivation of (a+b) * c for using the grammar, and also state
whether a given grammar is ambiguous one or not. (May 17)
E →E+E/E*E/(E)/id
This grammar G has two parse trees.
So it is said to be ambiguous grammar.
Parse tree 1: E=>E*E => (E) * E => (E+E) * E =>(a+E)*E =>(a+b)*E =>(a+b)*c
Parse tree 2: E=>E*E => E *c => (E) *c =>(E+E)*c =>(E+b)*c =>(a+b)*c
23. Let G be the grammar with the following productions (Dec 15)
S  aB / bA
A  aS / bAA / a
B  bS / aBB / b
Find leftmost derivation for the string aaabbabbba.
S  aB
=>aaBB
=>aaaBBB
=>aaabBB
=>aaabbSB
=>aaabbaBB
=>aaabbabB
=>aaabbabbS
=>aaabbabbbA
=>aaabbabbba
24. Define ambiguous grammar. (or) When do you say CFG is ambiguous. (Dec 19)
A CFG G such that some word has two parse trees is said to be ambiguous grammar.
In other words a CFG G has more than one leftmost (or rightmost) derivation for
given w is said to be ambiguous grammar.
25. Define unambiguous grammar.
If Grammar G has unambiguous, then for some w in L (G), there exists exactly
one parse tree. Hence, there exists exactly one LMD and equivalently one RMD.

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 17 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
26. Does a pushdown automaton have a memory? Justify. (May 16)
A PDA is similar to finite state machine, except that PDA has an auxiliary stack
which provides an unlimited amount of memory. Stack which is used to store the
necessary tape symbols and use the state to remember the conditions.
27. What are the primitives that are used to write the stack?
The primitives that are used to write the stack are:
 Push: adds the input alphabet to the top of the stack.
 Pop: Removes the top input alphabet from the top of the stack. If the stack is
empty, then a basic pop does not change the state of the stack.
 nop: Does nothing to the stack.
28. Define pushdown automata (PDA). (May 16) (Dec 19)
A PDA consists of 7-tuples M = (Q,,,,q0, Z0 , F),Where
Q - Finite set of states
 - Finite set of input symbols
 - Finite set of nonempty stack alphabets
qo - Initial state (q0 Є Q)
Z0 - Initial start symbol of the stack,
F - Set of accepting states or final states (F is subset of Q)
 - Transition function defined as  : Q()  Q*
29. List the components of pushdown automata (PDA)
The PDA is usually described as consisting of four components:
 Input tape: It is an infinitely long tape, on which input is written. The tape is
divided into sequence of cells. Each cell begins from the left end and extends to
the right, without an end.
 Read unit: Reads from the cells of the input tape, beginning with the first letter
in the leftmost cell, and then moves to the right.
 Control unit: It governs the operation of PDA by performing a sequence of
transitions between internal states available to it.
 Stack (Memory unit): It has an infinitely tall pushdown stack, which has last in
first out discipline.
30. What are the conventional notations of Pushdown Automata? (Dec 16)
 Symbols of the input alphabet will be represented by lower-case letters near the
beginning of the alphabet. e.g., a, b
 States will be represented q and p, typically, or other letters that are nearby an
alphabetical order
 Strings of the input alphabet will be represented by lower-case letters near the
end of the alphabet. e.g., w or z
 Stack symbols will be represented by capital letters near the end of the alphabet.
e.g., X or Y
 Strings of stack symbols will be represented by Greek letters. E.g., α or γ

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 18 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
31. What is the additional feature a PDA has when compared with NFA?
 Stack which is used to store the necessary tape symbols and use the state to
remember the conditions.
 Two ways of language acceptances, one reaching its final state and another by
emptying its stack.
32. What are the different ways languages acceptances by a PDA? (Dec 15)
The different ways languages accepted by PDA are
 Accept by final state
 Accept by empty stack
33. What are the two types of PDA?
 Deterministic PDA
 Nondeterministic PDA
34. Define the language accepted by final state.
After consuming the input, PDA enters a final state. The content of the stack is
irrelevant. For PDA M = (Q,,,,q0, Z0 , F) we define L(M), the language accepted by
final state, to be {w/ (q0, W, Z0) |-* (p,ϵ,γ) for some p in F and γ in }
35. Define the language accepted by empty stack.
After consuming the input, stack of the PDA will be empty. The current state
could be final or non-final state. For PDA M = (Q,,,,q0, Z0 , F) we define N(M), the
language accepted by empty stack or null stack to be {w/ (q0, W, Z0) |-*((p,ϵ, ϵ ) for some p
in Q}
36. Define Instantaneous description (ID) of PDA.
 The configuration of a PDA at a given instant is described by ID
 ID records the state and stack contents.
 ID is the triple (q,w,γ) where
q - State
w - String of input symbol
γ - String of stack symbol
37. Define deterministic PDA? (Dec 16)
A PDA is deterministic if each input string can only be processed by the
machine in only one way, i.e., for the same input symbol and stack symbol, there must
be only one choice. Formally, a PDA M = (Q,,,,q0, Z0 , F) is deterministic if
  (q,a,z) has only one element
  (q,ε,z) is not empty then  (q,a,z) should be empty.
38. Convert the following CFG to a PDA. S→ aAA, a→ aS| bS|a. (Dec 15)
The grammar is in GNF.
  (q0, ϵ, Z0) = (q1, SZ0)
  (q1, a, S) = (q1, AA)
  (q1, a, A) = (q1, S)
  (q1, b, A) = (q1, S)
  (q1, a, A) = (q1, ϵ)
  (q1, ϵ, Z0) = (q2, Z0)

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 19 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
39. Write rules for converting from CFG to PDA?
 Step 1: Without consuming any input, change the state to q1 and place the start
symbol of G onto stack. The transition defined is:  (q0, ϵ, Z0) = (q1, SZ0)
 Step 2:If there is a production of the form A→aα , then the corresponding
transition is :  (q1, a,A) = (q1, α)
 Step 3: In state q1, on encountering the end of the input, if Z0 is presents the stack
top, then change the state to q2 which is the final state and do not alter the
contents of the stack. The transition is defined as:  (q1, ϵ,Z0) = (q2,Z0)
 Note: Apply the above steps, only if the grammar is in GNF, otherwise the
grammar G has to be first converted to GNF.
40. Define the rule for construction of CFG from given PDA
 If q0 is the start state and qn is the final state of PDA then [q0Zqn]
becomes the start state of CFG. Z represents stack symbol.
 For (qi, a, Z0) = (qi+1, Z1Z2)
 (qi, Z0 qi+k) → a (qi+1 Z1 qm) (qm Z2 qi+k)
For (qi, a, Z0) = (qi+1, ) can be converted as (qi Z0 qi+1) → a
UNIT-III / PART-B
1. Construct a CFG to generate even and odd set of palindromes over alphabet {a,b} (Dec
17)
2. Generate CFG for the language L = {0i1j0k | j > i +k } (Dec 17)
3. Eliminate the Unit production of the following grammar (Dec 17)
S→A |bb
A→B |b
B→S |a
4. What do you mean by simplification of CFG? Explain with example.
5. Construct a context free grammar for the language L = {an / n is odd} (Dec 16)
6. Let G= (V,T,P,S) be a context free grammar then prove that if the recursive inference
procedure tells us that terminal string is in the language of variable A, then there is a
parse tree with root A and yield w. (Dec 15)
7. Given the grammar G =(V,∑,R,E) where
V = {1,2,3,4,5,6,7,8,9,0,+,-,*,/,(,)},
∑ = {E,D,1,2,3,4,5,6,7,8,9,0,+,-,*,/,(,)} and
R contains the following rules:
E→D|(E)|E+E|E-E|E*E|E/E
D→0|1|…|9
Find the parse tree for the string 1*2*3. (Dec 15)
8. What do you mean by derivation? Show the derivation steps and construct derivation
tree for the string „ababbb‟ by using LMD and RMD with the grammar S →AB| ε.
A→aB B→Sb (May 16)
9. Explain ambiguous and unambiguous grammar with example. (Dec 15) (May 16)
10. Define derivation tree. Explain its uses with an example. (Dec 16)

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 20 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
11. Explain the components of a PDA in detail. Also explain the description of a TM such as
transition diagram and transition table in detail.
12. Explain the ID of PDA? How will you represent it? Give the three important principles
of ID and their transactions and explain the languages accepted by PDA in detail.
(May 16) (Dec 16)
13. Explain acceptance by final state and acceptance by empty stack of a PDA. (May 16)
14. What are deterministic PDA and non-deterministic PDA? With example explain
deterministic PDA and non-deterministic PDA. (Dec 15)
15. (i) Construct a PDA for set of palindrome over the alphabet {a, b} or Construct a DPDA
for even length palindrome. (May 17)
(ii) Prove – If PDA P is constructed from CFG G by the above construction, then N (P)
=L (G). (May 17)
16. Construct a PDA accepting by empty stack the languages {anbn/, n1}. Draw the
transition diagram for the PDA. Show by instantaneous description that the PDA
accepts the string „0011‟. (Dec 15)
17. Construct a PDA to accept the following language L on  = {a,b} by empty stack.
L= {w wr| w Є } (May 16)
18. a) If L= N(PN) for some PDA PN =( Q,,,N,q0, Z0 ) then there is a PDA PF such that L=
L(PF) [From empty stack to final state]
b) Let L be L (PF) for some PDA PF = (Q,,,F,q0, Z0 , F). Then there is a PDA PN such
that L = N (PN) [From final state to empty stack]
19. Convert PDA to CFG. PDA is given by P =( {p,q}, {0,1}, ,q,Z) ,  is given by (p,1,z) =
{(p, XZ)}, (p, ϵ, z) = {(p, ϵ)},  (p,1,X) = {(p, XX)},(q,1,X) = {(q, ϵ )}, (p,0,X) = {( q, X}), 
(q,0,Z) = {(p, Z}) (Dec 15)
20. With an example, explain the procedure to obtain a PDA from the given CFG. (Dec 16)
21. Find PDA that accept the given CFG: (Dec 17)
S→xaax
X→ax/bx/ε
22. Construct PDA for the Language anbman+m. (Dec 17)
23. Convert the following CFG to PDA and verify for (a+b) and a++ (May 17)
I→a|b|Ia|Ib|I0|I1
E→I|E+E|E*E|(E)
24. Suppose L=L(G) for some CFG G=(V, T, P, S) then prove that L-{E} is L{ G‟} for a CFG
G‟ with no useless or epsilon production. (Dec 19)
25. Prove that the language accepted by PDA using empty stack and final states are
equivalent. (Dec 19)
26. i) Suppose L = N(m) for some PDA M, then prove that L is a CFL. (Dec 19)
ii) Give the CFG for the Language N(M) where M= ({q0, q1}, {0,1}, {Z0,x},,q0, Z0 }
UNIT IV PROPERTIES OF CONTEXT FREE LANGUAGES
Normal Forms for CFG – Pumping Lemma for CFL – Closure Properties of CFL – Turing
Machines – Programming Techniques for TM.

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 21 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021

UNIT-IV / PART-A
1. What do you mean by normal form? What are the two types of normal form of CFG?
When the productions in CFG are made to satisfy certain restrictions, then CFG is
said to be in normal form. Two types of normal forms are
 Chomsky normal form (CNF)
 Greibach Normal Form (GNF)
2. What is Chomsky Normal Form? (Dec 16)
A CFG is said to be in CNF if all productions are of the form A→BC or A→a where A,
B and C are non-terminals and „a‟ is terminal symbol.
3. What is GNF?
A CFG is said to be in GNF if all productions are of the form A→aX where a is terminal
symbol and X is a string of variables (possibly empty).
4. State Chomsky Normal Form theorem. (Dec 2016)
A context-free grammar G is said to be in Chomsky normal form (if all of its
production rules are of the form:
A → BC, or
A→a
where A, B, and C are nonterminal symbols, a is a terminal symbol (a symbol that
represents a constant value)
5. What are the closure properties of CFL?
CFL are closed under union, concatenation and Kleene closure. CFL are closed under
substitution , homomorphism.
CFL are not closed under intersection , complementation.
Closure properties of CFL‟s are used to prove that certain languages are not context
free.
6. State the pumping lemma for CFLs.
Let L be any CFL. Then there is a constant n, depending only on L, such that if z is in L
and |z| >=n, then z=uvwxy such that :
(i) |vx| >=1
(ii) |vwx| <=n and
(iii) for all i>=0 uviwxiy is in L.
7. What is the main application of pumping lemma in CFLs?
The pumping lemma can be used to prove a variety of languages are not context
free . Some examples are:
L1 ={ aibici | i>=1} is not a CFL.
L2= { aibjcidj | i>=1 and J>=1 } is not a CFL.
8. Give an example of Deterministic CFL.
The language L={anbn : n>=0} is a deterministic CFL
9. What are the properties of CFL?
Let G=(V,T,P,S) be a CFG
The fanout of G , Φ(G) is largest number of symbols on the RHS of
any rule in R.
The height of the parse tree is the length of the longest path from the root to some leaf.
10. Give an example of NonDeterministic CFL
The language L={ wwR : w Є {a,b} + } is a nondeterministic CFL.

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 22 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
11. What is a Turing machine? (May 16)
Turing machine is a simple mathematical model of a computer. TM has
unlimited and unrestricted memory and is a much more accurate model of a general
purpose computer. The TM is a FA with a R/W head. It has an infinite tape divided into
cells, each cell holding one symbol.
12. List the primary objectives of Turing machines. (Dec 16)
 Turing‟s objective was to demonstrate the inherent limitations of algorithmic
methods (An FA cannot accept {xcxr| x{a, b}*} and a PDA cannot accept
L = {anbncn| n  0} or L= {xcx| x{a,b}*}
 Every problem that can be solved on a real computer can also be solved by a
Turing machine
13. What is checking off symbols?
Checking off symbols is an effective way of recognizing the language by TM. I.e.
It is a useful trick for visualizing how a TM recognizes language defined by repeated
strings. It is also useful when lengths of substrings must be compared.
14. List the various techniques for TM construction.
 Storage in the finite control
 Multiple tracks
 Checking off symbols
 Shifting over
 Subroutines
15. Give the formal definition of a Turing Machine. (May 16) (Dec 15)
The Turing machine is represented as a 7-tuple M = (Q,,,,q0, B , F)
Q Finite set of states
 Finite set of input symbols
 Finite set of allowable tape symbols
q0 Initial state (q0 Є Q)
B Blank symbol,
F A set of final state (F is subset of Q)
 Transition function defined as :(Q ) ( Q L,R,N).
16. What are the components of TM?
A TM is usually described by the following three components:
 Tape: A tape is divided into sequence of numbered cells or squares, one next to
other. Each cell contains a symbol from some finite alphabet.
 Head: A tape head always stationed at one of the tape cells and provides
communication for the interaction between the tape and the control unit.
 Control unit: The reading from the tape or writing into the tape is determined by
the control unit.
17. What is shifting over?
TM can make space on its tape by shifting all non-blank symbols a finite number of
cells to the right. Or do so, the head makes an excursion to right repeatedly storing the
symbols read in its finite control and replacing them with symbols read from cells to the
left.

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 23 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
18. What are the differences between a finite automata and a TM? (May 16)
FA/PDA TM
The cells of the tape of FA or PDA are only The cells of the tape of TM may be written
read/scanned but never changed/written also.
into.
The tape head of FA or PDA always move The tape head of TM can move left to right
left to right and right to left also.
Outgoing transition from final state in FA Outgoing transition from final state is
or PDA is allowed. allowed.
19. Define Instantaneous description (ID) of Turing machine. (Dec 16)
The complete state of a TM, at any point during a computation, may be described
by
 The name of the state that in which the machine is
 The symbols on the tape and
 The cell that is currently being scanned.
A description of these three data is called instantaneous description (ID) or
configuration of a TM.
20. What is multi-head TM?
A TM with one tape and several heads on it is said to be a multi-head TM. The
use of multi-heads can sometimes simplify the construction of complex TMs drastically.
21. What is multiple tracks TM?
 Multiple tracks, each cell of the tape is assumed to be split vertically and each split
part is called as a track, generally two tracks are used, one track is used to hold the
data and the other track is used to keep track of the symbols already read.
 A single head, capable of reading symbols in all the tracks of a cell.
 The tape head of the TM can remember a symbol if required.
 The advantage is that one track can be used to mark the already visited cells, so that
the number of forward and reverse movement of the tape head can be reduced then
compared to a single tape head TM.
22. Define subroutines in TM.
As with programs, a modular or top down design is facilitated, if we use
subroutines to define elementary processes. Generally subroutines are designed separately
and used in the main program. The subroutine is called by giving the initial state and final
state of the subroutine in a block.
23. What is two way infinite TM?
A TM in which there is an infinite number of sequences of blanks either side of the
tape is said to be two-way infinite tape TM. The advantage of having this type of TM is that
there is no possibility of jumping off the left end of the tape.
24. Is it possible that a Turing machine could be considered as a computer of functions from
integers to integers? If yes justify
TM is viewed as a computer of functions from integer to integer. The traditional
approach is to view integer in unary format. The integer is represented by the string 0i.
Example. The integer 3 is represented as 03=000.If the function has k arguments then these
integers are separated by 1.

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 24 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
25. List out different types of TM Or Extensions of TM Or modification of TM.
 Two way infinite tape TM
 Multi tape TM
 Multi head TM
 Multidimensional TM
 Off-line TM
 Non-deterministic TM and
 Universal TM
26. What is multi-tape TM? (Dec 15)
A TM with more than one tape and each tape having its own independent head is
said to be a multi-tape TM. Formally it is represented as a 7-tuple M = (Q,,,,q0, B , F)
where  is the Transition function defined as  : Qk  Q k L,R, k (k is the number of
tapes)
27. List the Chomsky hierarchy of languages.
Noam Chomsky, the founder of formal language provided the classification for
grammars as given below:
Type 0 - Unrestricted grammar
Type 1 - Context sensitive grammar
Type 2 - Context free grammar
Type 3 - Regular grammar
28. What is non-deterministic TM (NTM)?
A NTM is a device with a finite control and a single one way infinite tape. For a
given state and tape symbol the machine has a finite number of choices for the next
move. Each move consists of a new state, tape symbol to print, and a direction of head
move. The transition of NTM is represented as:  (q,s) = (qi,si,Mi) for i = 1, 2,….
Where q current state
s symbol being scanned by the tape head and
M move
29. What is off line TM?
An off line is a multi-tape TM, whose input tape is of type read-only. The input is end
marked by a Φ on the left and $ on the right. The TM is not allowed to move the input
tape head, off the region between Φ and $. An offline TM can simulate any TM T, by
using one more tape.
30. Give the configuration of Turing machine. (Dec 17)
A configuration for a Turing machine is an ordered pair of the current state and
the tape contents with the symbol currently under the head marked with underscore.
For example (q, aababb) shows that the Turing machine is currently in state q, the taper
contents are the string aababb and the head is reading the last a of the string. We write
( p , xay ) ( q , zbw ) if the Turing machine goes from the first configuration to the
second in one move, and ( p , xay ) * ( q , zbw ) if the Turing machine goes from the
first configuration to the second in zero or more moves. If the Turing machine needs to
be explicitly indicated T or T* is used.

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 25 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
31. What are the advantages of having normal form for a grammar? (Dec 19)
 Parsers can use binary trees.
 Exact length of derivations is known
32. Define the language recognized by Turing machine. (Dec 19)
 If the string is in the language, then the TM halts in a final state.
 If the string is not in the language, then the TM may halt in anon-final state or
never halt.
33. When do you say turning machine is an algorithm? (Dec 19)
Alan Turning is the first person who studied algorithms mathematically by creating a
universal machine model, later called Turing machine.
UNIT-IV / PART-B
1. Obtain the Greibach Normal form for the following grammar G= ({A 1,A2,A3},{a,b},P,A1 )
where P consists of the following A1A2 A3, A2A3 A1/ b , A3A1A2/ a
2. Construct a equivalent grammar G in CNF for the grammar G1 where
G1=({S,A,B},{a,b},{S→ASB| ε, A→aAS|a, B→SbS|A|bb},S). (Dec 15)
3. What is the purpose of normalization? Construct the CNF and GNF for the following
grammar and explain the steps. (May 16)
S→aAa|bBb| ε,
A→C|a
B→C|b
C→CDE|ε
D→A|B|ab
4. Obtain a grammar in Chomsky Normal Form (CNF) equivalent to the grammar G with
the productions P given. (Dec 16)
S→aAbB
A→aA|a
B→bB|b
5. Begin with the grammar
S→ 0A0 | 1B1 | BB
A→ C
B →S|A
C→S| and simplify using safe order Eliminate  production, unit production and
useless symbol and put the grammar in Chomsky‟s normal form
6. Explain the components of a TM in detail. Also explain the description of a TM such as
transition diagram and transition table in detail.
7. Explain the ID of TM, moves of TM, string classes in TM, Languages accepted by TM in
detail.
8. Find an equivalent grammar in CNF for the grammar (Dec 17)
S→bA |aB
A→bAA|aS|a
B→aBB |bS |b

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 26 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
9. Given the CFG G, find CFG G‟ in CNF generating the language L(G) = {^} (May 17)
S→AACD
A→aAb|^
C→aC|a
D→aDa|bDb|^
10. Convert the following grammar G into Greibach Normal Form (GNF) (May 17)
S→XA|BB
B→b|SB
X→b
A→a
11. Construct a TM for the language L= {anbn/n ≥0}.Draw the transition diagram.(Also
specify the instantaneous description to trace the string 0011) (Dec 15)
12. Construct a TM for the language L= {anbncn/n ≥0}.
13. Construct a TM to compute a function f(w)= WR where W ε {a,b}+ or Construct a Turing
machine to reverse the given string. (May 17)
14. Describe Chomsky hierarchy of languages with example. What are the devices that
accept these languages? (May 16) (Dec 15) (Dec 17)
15. Explain the various (programming) techniques for Turing machine construction.
(Dec 15) (Dec 16) (Dec 17)
16. Explain the variations of Turing machines. (May 16). Write about Multi Tape Turing
machines. (Dec 16) Explain Multi tape and Multi head Turing machine with suitable
example. (May 17)
17. Construct a Turing machine compute multiplication with subroutine “copy”
18. Design a Turing machine which recognizes palindrome over alphabet {a,b}.Trace the
strings “abab” and “baab”. (May 16)
19. Explain TM as a computer of integer functions with an example.(proper subtractions).
(Dec 19)
20. Construct Turing machine (TM) that replace all occurrence of 111 by 101 from sequence
of 0's and 1's. (Dec 17)
21. State and prove Greibach Normal Form. (Dec 19)
22. i) Design a Turing machine to computer multiplication of two positive integers.
ii) Design a Turing machine to recognize the language {0n1n0n for n>=1} (Dec 19)
UNIT V UNDECIDABILITY
Non Recursive Enumerable (RE) Language – Undecidable Problem with RE – Undecidable
Problems about TM – Post„s Correspondence Problem, The Class P and NP.
UNIT-V / PART-A
1. List the properties of recursive and recursively enumerable languages?
 The complement of a recursive language is recursive,
 The unions of two recursive languages are recursive.
 The unions of two recursively enumerable languages are recursively
enumerable.
 If a language L and are both recursively enumerable then L is recursive.

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 27 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
2. What is primitive recursive function?
A function f (x1, x2…xn) is primitive recursive if either:
 f is a function that always 0 i.e. f (x1, x2…xn) =0
 f is the successor function i.e. f (x1, x2…xn) = xi +1
 f is the projection function i.e. f (x1, x2…xn) = xi
 f is defined by the composition of primitive recursive functions
 f is defined by recursion of two primitive recursive functions
3. Define diagnalization language Ld?
Diagnalization language Ld is the collection of Turing machines programs M
such that M does not halt and accept when given itself at input. Ld = {M/M L(M)}
4. Define recursive language.
A language is recursive if there exists a Turing machine that accepts every string
of the language and rejects every string (over the same alphabet) that is not in the
language.
5. What is meant by RE languages?
A language is recursively enumerable if there exists a Turing machine that
accepts every string of the language, and does not accept strings that are not in the
language. (Strings that are not in the language may be rejected or may cause the Turing
machine to go into an infinite loop.)
Clearly, every recursive language is also recursively enumerable. It is not
obvious whether every recursively enumerable language is also recursive.
6. When is a recursively enumerable language said to be recursive? (May 16)
A language is recursive if there exists a Turing machine that accepts every
string of the language and rejects every string (over the same alphabet) that is not in
the language. A language is recursively enumerable if there exists a Turing machine
that accepts every string of the language, and does not accept strings that are not in
the language.
7. Show that union of recursive language is recursive
L1 and L2 are recursive language. Then there exists a machine M1 that accepts L1 as
well as machine M2 that accepts L2. We can simulate a machine M that accepts the language
L such that L = L1 U L2. Then construct M which accepts if M1 accepts. If M1 does not accept
then M2 simulates M. That means if M2 accepts then M accepts, if M2 rejects M also rejects.
Thus M accepts the language L = L1 U L2 which is recursive.
8. State when a problem is said to be decidable problem and give example. (Dec 15)
A problem whose language is recursive is said to be decidable. (Or) A decision
problem that can be solved by an algorithm (and halts on all inputs in a finite number of
steps) is called decidable problem. Example: Whether a FA accepts the string, whether two
FA are equivalent.
9. State when a problem is said to be undecidable problem and give example.
A problem is undecidable if there is no algorithm that takes as input as instance of
the problem and determining whether the answer to that instance is yes or no.
Example: Halting problem, PCP, RICE theorem.

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 28 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
10. What is Universal language Lu? (Dec 15)
Universal language Lu is the set of all strings wi such that wi Є L (Mi) (Or) Lu to be {<M, W>
/ M accepts W}
11. Define PCP.
An instance of posts correspondence problem consists of two lists,
A = w1, w2, w3…wk,
B = x1, x2, x3…xk of strings over some alphabet . This instance of PCP has a
solution if there is any sequence of integers i1, i2…im with m ≥1 such that
.
The sequence i1, i2…im is a solution to this instance of PCP.
12. State RICE theorem.
If R is a property of languages that is satisfied by some but not all recursively
enumerable languages, then the decision problem
PR: Given a TM T, does L (T) have property R?
is unsolvable.
13. What is Universal Turing Machine? (Dec 16)
Turing machines were designed to solve a particular problem and for each type of
problem a different Turing machine is required. The idea of universal Turing machine has
lead the idea of having unique machine to solve all the types of problem. The idea of UTM
is similar to stored program concept.
14. Define class P.
Class P is set of all decision problems than can be solved by deterministic Turing
machine using a polynomial amount of computation time. Example: Decision versions of
linear programming, Calculating GCD, Finding a maximum matching, Determining the
number is prime
15. Define tractable problem. Give example.
A problem that is solvable by a polynomial time algorithm is known as tractable
problem. (The upper bound is polynomial) Example: searching an unordered list, Searching
an ordered lists, sorting a list, multiplication of integers, finding MST in a graph.
16. Define intractable problem. Give example. (Or) Identify whether ‘Tower of Hanoi’
problem is tractable or intractable. Justify your answer. (May 16)
A problem that cannot be solved by a polynomial time algorithm is known as
intractable problem. (The lower bound is exponential) Example: Tower of Hanoi, (we can
prove that any algorithm that solves this problem must have a worst-case running time that
is at least 2n-1), Listing all permutations of n numbers.
17. Define class NP. (Dec 19)
Class NP is set of all decision problems than can be solved by Non-deterministic
Turing machine using a polynomial amount of computation time. Example: Traveling
salesman problem, Hamiltonian circuit
18. State halting problem.
Halting problem is a decision problem which can be informally stated as: „Given a
description of a program and a finite input, decide whether the program finishes running or
will run forever‟. Formally it is stated as: „Given an arbitrary machine M and a string W,
does M halt with W as the input string?‟

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 29 of 30
 CS8501- Theory of Computations Department of CSE 2020-2021
19. Define Polynomial time reduction.
The principle methodology for proving a problem P2 cannot be solved in polynomial
time (i.e. P2 is not in P) is the reduction of a problem P1, which is known, not to be in P, to P2. A
reduction from P1 to P2 is polynomial time if it takes time that is some polynomial in length of
the P1 instance.
20. Is halting problem decidable or undecidable problem
Formally it is stated as: „Given an arbitrary machine M and a string W, does M halt with W as
the input string?‟ The halting problem is unsolvable. Hence it is undecidable problem.
21. Define NP-Hard. (Dec 16)
A decision problem Pi is NP-hard if every problem in NP is polynomial time reducible
to Pi. In symbols Pi is NP-hard if, for every Pj Є NP, Pj poly Pi (Note all NP-complete problems
are NP-hard, but some NP-hard problem are not known as NP-complete)
22. Define NP-Complete. (Dec 16)
A decision problem Pi is NP-complete if
 It is NP-hard
 It is also in the class NP itself.
In symbols Pi is NP-complete if Pi is NP-hard and Pi Є NP.
Example: Vertex cover problem, Hamilton circuit problem, Integer linear programming
problem, Chromatic number problem, Traveling salesman problem
UNIT-V / PART-B
1. Elaborate on primitive recursive functions with an example (Dec 16)
2. Describe about Recursive and RE languages in detail. Also discuss the properties of recursive
and RE in detail. (Dec 15) (Dec 16) (May 17)
3. Show that the union of two recursive language is recursive and union of two RE language is
recursive.
4. Show that the language Lu is RE language. Show that the language Ld is not RE language.
5. What is PCP? Explain with the help of an example. (May 16)
6. Explain the universal Turing machine with its significance. Also explain the construction of
Universal Turing machine with example. (May 16) (Dec 17)
7. Explain decidable and undecidable problem with example.
8. a)State and explain RICE theorem. (Dec 15)
b) Prove that MPCP reduces to PCP. (Dec 15)
9. Explain tractable problem and intractable problem with example. (Dec 15) (Dec 16) (May 17)
10. Outline the concept of polynomial-time reductions. (Dec 16)
11. Explain class P, class NP, NP-complete and NP-hard problem with examples in detail.
12. Explain halting problem. Is it solvable or unsolvable problem? Discuss. (May 16) (Dec 15) OR
Highlight the implications of halting problems. (Dec 16) OR Prove that Halting problem is
undecidable. (Dec 17)
13. Explain how to measure and classify complexity. (Dec 17)
14. Consider two-tape Turing machine and determine whether the Turing machine always writes a
nonblank symbol on its second tape during the computation on any input string. Formulate this
problem as s language and show it is undecidable. (Dec 17)
15. Prove that Post Correspondence problem is undecidable. (Dec 19)
16. Prove that Universal Language LU is recursively enumerable but not recursive. (Dec 19)

St. Joseph’s College of Engineering & St. Joseph’s Institute of Technology Page 30 of 30