THEORY OF COMPUTATION
ASSIGNMENT - 01
Q-1 Define one-to-one, onto and bijection function.
Q-2 Explain Compositions and Inverse of functions.
Q-3 Explain reflexivity, symmetry, and transitivity properties of relations. Prove that √2
is Irrational by method of Contradiction.
Q-4 Check whether the function is one to one and onto.
Q-5 Consider the relation R = {(1,2), (1,1), (2,1), (2,2), (3,2), (3,3)} defined over {1, 2,
3}. Is it reflexive? Symmetric? Transitive? Justify each of your answers.
Q-6 State the principle of mathematical induction and prove by mathematical induction
that for all positive integers n 1+2+3+……. +n = n (n+1)/2.
Q-7 Using Principle of Mathematical Induction, prove that for every n >= 1
Q-8 What are the closure properties of regular languages?
Q-9 Define Mathematical Induction Principle and Prove that for every n ≥ 1,
Q-10 State the principle of mathematical induction and prove by mathematical induction
that for all positive integers n 1+2+3+……. +n = n (n+1)/2.
THEORY OF COMPUTATION
ASSIGNMENT - 02
Q-1 Write RE for the languages of all Strings that do not end with 01.
Q-2 Compare FA, NFA and NFA-^
Q-3 Draw a FA for following regular language.
(i) (11+110)* 0 (ii) (0+1)*(10+11)
Q-4 Design a Moore machine to determine residue number 3 for binary number
Q-5 Write Kleene’s Theorem Part-I, any regular language can be accepted by a finite
automation
Q-6 Define DFA and NFA and NFA- Λ
Q-7 Consider the NFA-Λ depicted in following table:
a. Compute the Λ-closure of each state.
b. Convert the NFA-Λ to a DFA
Q-8 Use Pumping Lemma to show that L = {x Є {0,1}*| x is a palindrome} is not a
regular language.
Q-9 Fig. shows two DFAs M1 and M2, to accept languages L1 and L2, respectively.
Determine DFAs to recognize L1 U L2.
Q-10 Convert the NFA given in Table below to its corresponding DFA and draw the
DFA
Q-11 Convert the Mealy machine shown in given figure into Moore machine.
Q-12 Draw FA for accepting:
(i)The string in {0,1}* ending in 1 and not containing substring 00.
(ii)The strings with odd no of 1’s and odd no of 0’s
THEORY OF COMPUTATION
ASSIGNMENT - 03
Q-1 Define CFG. When is a CFG called an ‘ambiguous CFG’?
Q-2 Consider following grammar:
Give leftmost and rightmost derivations of the string 00101. Also draw the parse tree
corresponding to this string.
Q-3 Prove that the following CFG is Ambiguous.
S -> S + S | S * S | a | b
Write the unambiguous CFG based on precedence rules for the above grammar. Derive the
parse tree for expression (a + a)*b from the unambiguous grammar.
Q-4 Explain Union Rule and Concatenation Rule for Context Free Grammar.
Q-5 Given the Context Free Grammar G, find a CFG G’ in Chomsky Normal Form generating L(G)
–{}
S → aY | Ybb | Y
X → /\ | a
Y → aXY | bb | XXa
Q-6 Consider following grammar:
S →ASB | Λ
A →aAS | a
B→SbS | A | bb
i. Eliminate useless symbols, if any.
ii. ii. Eliminate Λ productions
Q-7 What is CNF? Convert the following CFG into CNF.
S → ASA | aB,
A → B | S,
B→b|ε
Q-8 Define grammar and Chomsky hierarchy
Theory of Computation (3160704)
UNIT-4
1. Explain push down automata with example and their application in detail.
2. For the language L = { xcxr | x Є {a,b}* } design a PDA(Push Down Automata).
3. Convert the following grammar to a PDA:
E -> A | E * E | E + E | (E)
A -> a | b | Aa | Ab | A0 | A1
4. Given a CFG , G =( {S,A,B},{0,1},P,S) with P as follows
S --> 0B| 1A A --> 0S|1AA|0 B --> 1S| 0BB |1
Design a PDA M corresponding to CFG, G. Show that the string 0001101110
belongs to CFL, L(G).
5. Using pumping lemma for CFL’s, show that the language L = {am bm c n | m ≤ n ≤
2m} is not context free.
6. Write PDA for following languages: { ai bj c k | i, j, k >= 0 and j = i or j = k}.
7. Design and draw a deterministic PDA accepting strings with more a’s than b’s. Trace
it for the string “abbabaa”.
8. Design a PDA, M to accept L = { an b2n | n ≥ 1 }.
Theory of Computation (3160704)
UNIT-5
1. What is Turing Machine. Give definition of Turing Machine.
2. Draw a Turing Machine (TM) to accept Even and odd Palindromes over {a,b}.
3. Explain Universal Turing machine with the help of an example
4. Write a Turing Machine to copy strings.
5. Explain Church Turing Hypothesis.
6. Define grammar and Chomsky hierarchy.
7. Draw a transition diagram for a Turing machine accepting the following language:
{ an bn c n | n ≥ 0 }
8. Design a Turing machine for the language over {0,1} containing strings with equal
number of 0’s and 1’s.
Theory of Computation (3160704)
UNIT-6&7
1. Describe recursive languages and recursively enumerable languages.
2. Briefly describe following terms: (1) Halting problem
(2) Undecidable problem
(3) P Class Problem
3. Explain primitive recursive function by suitable example.
4. Define Initial function. Explain types of initial functions by suitable example.
5. Define functions by Primitive Recursion. Show that the function f(x, y) = x + y is primitive
recursive.
6. Differentiate between NP Complete and NP Hard Class.
7. Ackerman’s Function is defined as:
Solve for A(1,2), A(2,1) and A(2,2).
