Department of Computer Science & Engineering)

Subject Name- Theory of Computation

Subject Code- 22CST-353
Assignment -1 (Mapped with CO4, CO5)

Set –A
S. no Question Marks COs BT
Level
1. Construct DFA to accept the following languages over alphabet {0, 1} 5 Marks CO4 Level 5

a. The language of all strings containing at least three 1’s.

b. The language of all strings that do not end with 11.

2. Consider the following NDFA/NFA whose transition table is given and design 5 marks CO5 Level 6
DFA.Q= {q0, q1, q2, q3}, ∑={a,b}. Here q0 is the initial state and q3 is the final
state.

Explain the procedure step by step.

 Set –B
S. no Question Marks COs BT
Level
1. . 5 marks CO4 Level 5
a. Consider the transition diagram given below & convert given NFA-ε to
NFA

2. 5 marks CO5 Level 4

 SET-C
S. no Question Marks COs BT
Level
1. Consider a Mealy machine 5 CO4 Level 5
mark
s

a. Construct Transition table for this given Mealy Machine

b. Find Output for input 001
c. Construct a Moore machine equivalent to this Mealy machine

2. 5 marks CO5 Level 6

Explain the procedure step by step and design Minimized DFA.

 Fast learner Assignment
based on
MST-1
Subject Name Theory of Computation
Subject Code 22CST-353

Q1.

Compute the ε–closure of each state.

Q2.

Find the language accepted by following DFA.

Q3.
Construct the Context free grammar representing the set of palindromes over
(0+1)*.

Q4.
Identify the place of Grammars, Languages and Machines in Venn diagram of Chomsky
hierarchy.
Q5.
Construct the minimum state automaton equivalent to the transition diagram

Q6.
Convert the following Null-NFA to its equivalent DFA.

Q7.

Let L = {w:w ε {0,1}* w does not contain 00 and is not empty}. Construct a regular expression
that generates L.

Q8.

Discuss the procedure to convert Moore Machine to Mealy machine and convert following Moore
Machine to Mealy Machine.
Q9.

Prove by pumping lemma, that the language 0n1n is not regular.

Q10.

Prove that the language L = {a^n b^m | n < m} is not regular using the pumping lemma
 Assignment-2
Average Learners
Subject Name Theory of Computation
Subject Code 22CST-353

SET-A
Q1.
Using Pumping Lemma prove that the Language A=(YY| Y->{0,1}*) is not Regular.

Q2.
Show that id+id*id can be generated by two distinct leftmost derivation in the grammar
E->E+E | E*E | (E) | id

Q3.
Find a reduced grammar equivalent to the grammar G by removing useless symbols
whose productions are

Q4.
Let L = {w:w ε {0,1}* w does not contain 00 and is not empty}. Construct a regular expression
that generates L.

Q5.
Construct NFA equivalent to the regular expression (0+1)01
 SET-B
Q1.
How can you prove that a given language is not regular by the Pumping lemma? Write
down proper steps.

Q2.
Let G be the grammar:
S->aB/bA, A->a/aS/bAA, B->b/bS/aBB. obtain parse tree for thestring aaabbabbb

Q3.
Analyse Arden’s Theorem. Find regular expression for the following DFA using Arden’s
theorem.

Q4.
Discuss the terms null production and unit production with an example.

Q5.

Construct a minimized DFA from the regular expression

(i) (b/a)*baa

(ii) 0*(01)(0/111)*
 Slow learner Assignment
based on
MST-1
Subject Name Theory of Computation
Subject Code 22CST-353

Q1. Elaborate the operations performed on various formal languages.

Q2 Construct a DFA for the language over {0, 1}* such that it contains “000” as a

substring.

Q3 Draw the transition diagram for an identifier.

Q4 Draw a Non-deterministic finite automata to accept strings containing the substring

0101.

Q5 Mention the need to minimize Finite Automata?

Q6 Distinguish CNF and GNF with examples.

Q7 Discuss the purpose of normalization? Construct the CNF and GNF

for the following grammar and explain the steps.
S→aAa | bBb |€ A→C|a B→C|b C→CDE | € D→A|B|ab

Q8 Construct DFA equivalent to the NFA given below and specify its regular Expression:
Q9 Consider a Mealy machine

a) Construct Transition table for this given Mealy Machine

b) Find Output for input 001
c) Construct a Moore machine equivalent to this Mealy machine

Q10 Explain the applications of regular expression?

 Assignment-3
Fast learner based on MST-2
Subject Name Theory of Computation
Subject Code 22CST-353

Q1 Design the CFG for the language L= (an bn | n>1)

Q2 Construct a reduced grammar by removing useless symbols equivalent to the grammar

Q3 Construct NFA For Regular Expression R=(01)*(10)*+00*

Q4 Discuss steps to normalize CFG.Design the following grammar into equivalent one
with no unit production and no useless symbols and convert into CNF.
S->A|CB A->C|D
B->1B|1
C->0C|0 D->2D|2

Q5 Convert given DFA to Regular Expression.

Q6 Construct PDA for the language L = {wwR | W in (a+b)*)}

Q7 Is it true that the language accepted by a non deterministic Turing Machine is different
from recursively enumerable language?

Q8 Construct PDA which accepts language

L={wwr |w∊{a,b}+ r is any positive integer}

Q9 Design a TM to accept the language LE={a n b n | n >= 1 }

Q10 Discuss basic guidelines to design the Turing Machine. Develop a Turing machine to

Recognize all strings consisting of an even number of 1’s.

 Assignment-3
Average learner based on MST-1
Subject Name Theory of Computation
Subject Code 22CST-353
S. no Question Marks COs BT
Level
1. Discuss the Acceptability of Pushdown automata. 2 CO5 5

2. Consider the push down automaton 2 CO4 6

M = ({q0, q1}, {0, 1}, {0, 1, Z0}, , Z0, q0, {q1}).
T1 : (q0, 0, Z0) = {(q1, Z0)}
T2 : (q0, 0, 1) = {(q0, 01)}
T3 : (q0, 1, 1) = {(q1, )}
T4 : (q1, 1, 0) = {(q1, 10)
T5 : (q1, 0, 0) = {(q1, )}

Construct context free grammar equivalent to it.

3. Design a TM to accept the language LE={a n b n | n >= 1} 2 CO5 6

4. Explain steps to prove that the Post Correspondence problem is Undecidable. 2 CO5 2

5. Interpret the statement that a recursively enumerable language is said to be 2 CO5 3

recursive.

6. Q1 Differentiate between Deterministic PDA and Non– deterministic PDA 2 CO5 3

7. Convert the following CFG to a PDA 2 5

S→aAA, A→aS|bS|a CO5

8. Construct PDA which accepts language 2 CO5 6

L={wwr |w∊{a,b}+ r is any positive integer}

9. Discuss language accepted by the Turing machine. Construct a Turing Machine 2 CO5 6
for
language L = {wwr | w ∈ {0, 1}}
10. State when a problem is said to be decidable and give an example of an 2 CO5 3
undecidable
problem.
 Assignment-3
Slow learner based on MST-2
Subject Name Theory of Computation
Subject Code 22CST-353
Q1 Let the production of the grammar be S-> 0B | 1A, A-> 0 | 0S | 1AA, B-> 1|1S |0BB. For
the string 0110 find the right most derivation.
Q2 Differentiate between ambiguous and unambiguous grammars and prove that following
grammars are ambiguous.
a) E->E+E/E*E/(E)/id
b) S->SS/(S)/a/∧

Q3 State rules to remove null-productions from CFG. Consider the grammar G whose
productions are

Remove null Productions from this given grammar.

Q4 Convert the given CFG into CNF.

Q5 How can you prove that given language is not regular by Pumping lemma? Write down
proper steps.

Q6 a) Define Instantaneous description (ID) in PDA.

b)Explain about the graphical notation of PDA
Q7 Construct PDA which accepts language
L={anb2n|w∊{a,b}+}

Q8 Explain the various types of Turing machine.

Q9 Construct a Turing Machine for language L = {wwr | w ∈ {0, 1}}

Q10 a) Define PCP. Verify whether the following lists have a PCP solution.

b) Describe linear bounded automaton.