Question Bank

Course & Branch : CSE Semester: 6

Subject : Theory of Computation Subject Code: CST-352

No. of Students: 960 Regular/ Reappear:Regular

Note: 1. Fill the details in the above table correctly.

2. Do not delete/move the position of chapter and its difficulty level in the below format of question bank.

3. Type the question by making virtual chapter of the Unit (if unit not divided into chapters)and proper
difficulty level in the appropriate cell so that from each chapter the question may be selected for Tests.
4. For long Answer type questions, HODs are requested to decide that how many subparts are required for
their course i.e. 2 subparts or 3, keeping in consideration the level of Question.
5. All the sub parts, equations, pictures if any are to be placed in the same cell of the table for the same
question.
6. Do not leave any cell blank
7. Do not repeat the question which may leads to duplicate question in Test
8. Do not repeat the similar question in short and in long answer type question.

Short Answer Type Questions

 Question
Sr. No Question
Type

Unit -1 Construct a finite automaton for the regular expression 0(1+0)*

1

Unit -1 Give the DFA accepting the language over the alphabet 0, 1 that has the set of all strings
2
beginning with 10.

Consider the finite automaton whose transition diagram is given below, check whether 110001
will be accepted or rejected by machine.

Unit -1
3

Unit -1 Write the difference between the Kleene closure and Kleene plus.
4

Unit -1 Construct DFA for the language of all strings in which every 0 is immediately followed by 1.
5
 Unit -1 Give English descriptions of the languages of the regular expression (0+1)(0+1)*.
6

Unit -1 If L is a set of all strings over {a, b} starting with a. Find Complement of L and Reversal of L.
7

Unit -1  if L={a,bb}, Find

8

Unit -1 Every DFA is NDFA. Justify this statement.

9

Unit -1  If L is set of all strings over {0,1} ending with 01, find the corresponding regular expression.
10

Unit -2  Construct a CFG for the language of odd length palindrome string over {a, b}.
11

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

Unit -2  Mention the application of CFG.

13
 Unit -2 What are the two normal forms of CFG?
14

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

Unit -2
15 the string aaabbabbba

Unit -2 State Pumping Lemma.

16

Unit -2 Differentiate between Finite Automaton with output and without output with example.
17

 Let the production of the grammar be S-> 0B | 1A, A-> 0 | 0S | 1AA, B-> 1|1S |0BB. For the
Unit -2
18 string 0110 find the right most derivation

 Construct a derivation tree for the string 0011000 using the grammar S->A0S |0 | SS ,
Unit -2
19 A-> S1A|1

Unit -2  Write the CFG for the language L= (a n bn | n>1)

20

Unit-3 Give one example of non-deterministic context free language.

21
 Unit-3 Give one example of a language that is CFL but not regular language.
22

Unit-3 Differentiate between PDA and Turing Machine tape movement.

23

Unit-3 Mention any two problems which can only be solved by TM but not by PDA.
24

Unit-3 Give an example of Type 2 grammar.

25

Unit-3 Give correlation between grammar and languages.

26

Unit-3 List out applications of PDA.

27

Unit-3  Write down role of stack in Push Down Automaton.

28

Unit-3 State MPCP Problem.

29
 Unit-3 State PCP Problem.
30

Long Answer Type Questions

Sr. Question
Question
No Type

 Construct DFA to accept the following languages over alphabet {0, 1}

Unit -1
1
Average a) The language of all strings containing at least three 1’s.
b) The language of all strings that do not end with 11.
c) The language of all strings containing even number of 1’s.
d) The language of all strings containing number of 1’s divisible by 4
e) The language of all strings of length two.

If set of input symbols contains {0,1} and the given language contains all the strings beginning
with 1 and not having two consecutive 0’s.
Unit -1
2 (a) Build a regular expression satisfying the above mentioned constraints.
Average
(b) Also Construct a FA equivalent to regular expression created in step (a).

3 Unit -1 Describe five tuples of DFA and construct a DFA equivalent to the NFA M=({p,q,r},{0,1}, δ ,p,
Average {q,s})
where δ is defined in the following table
 0 1

P {q,s} {q}

Q {r} {q,r}

R {s} {p}

S - {p}

4 Unit -1 (a) Construct a DFA accepting all strings w over {0,1} such that the number of 1’s in w is 3
Average mod 5.
(b) Identify initial and final states in NDFA M given below and also show whether it accepts
a string 01110 or not.
  Write down five tuples of Non-Deterministic Finite Automaton. Also, convert the following NFA
to a DFA

Q\Σ 0 1

P {p,q} P
Unit -1
5
Average

Q r R

R s -

S s S

6 Unit -1  Are DFA and NDFA equivalent in power? If yes, construct a deterministic automaton
 equivalent to the NDFA represented by the table shown under:

Average

Unit -1 Differentiate between DFA, NDFA and NDFA with null transitions. Also, explain 5 tuples of these
7
Average machines in detail. 

(a) Give notion of string acceptance by Deterministic Finite Automaton.

(b) Construct DFA equivalent to the NFA given below

Unit -1
8
Average

Convert the following NDFA/NFA to DFA whose transition table is given.

Q= {q0, q1, q2, q3}, ∑={a,b}. Here q0 is the initial state and q3 is the final state.

Unit -1
9
Average

Explai
n the procedure step by step.
  State Arden’s theorem. Also find the regular expression corresponding to the given automaton

Unit -1
10
Average

Construct a DFA equivalent to the NDFA M whose transition diagram is given below

Unit -1
11
Difficult

Define Regular Expressions and construct a DFA equivalent to the regular expression
Unit -1 (0+1)*(00+11)(0+1)*
12
Difficult

Give significance of + and * operators in regular expressions and Construct a FA equivalent to

Unit -1 the regular expression
13
Difficult
11+ (1+00)0*1.
 a) How NFA is different from NFA with null transitions.
b) Construct a NFA accepting language represented by the regular expression

Unit -1
14
Difficult

((0+1)*11)+ 0*1)

 The transition table of a nondeterministic finite automaton M is defined by Construct a

deterministic finite automaton equivalent to M

Unit -1
15
Difficult

 M = ({q1, q2, q3}, {0,1}, transition function, q1, {q3}) is a nondeterministic finite
Automaton where transition function is given by

Unit -1
-16
Difficult

Construct an equivalent DFA

17 Unit -1  Find regular expression for finite automaton whose transition diagram is as shown as below
Difficult and show that it accepts the set of all strings over the alphabet {a, b} with an equal number of
a's and b's, such that each prefix has at most one more a than the b's and at most one more b
than the a's.
 Describe in English the set accepted by the finite automaton whose transition diagram is as
shown below

Unit -1
18
Difficult

Also, represent the language accepted by this FA by regular expression.

State Arden Theorem and construct a regular expression corresponding to the state diagram
described by

Unit -1
19
Difficult
 Given transition diagram below represents a DFA. Justify this statement and find the regular
expression corresponding to Finite Automaton.

Unit -1
20
Difficult

 State Kleene theorem and construct the finite automaton equivalent to the regular expression
Unit -1
21 10+(0+11)0*1.
Difficult

 For each of the following languages give Regular Expression

Unit -1
22
Difficult

23 Unit -1  In each part below, draw an FA accepting the indicated language over {a, b}
Difficult
 a) The language of all strings containing exactly two a’s.
b) The language of all strings containing at least two a’s.
c) The language of all strings that do not end with ab.
d) The language of all strings that begin with aa.
e) The language of all strings containing the substring aa.

 In each part below, draw an FA accepting the indicated language over {a, b}

Unit -1
24
Difficult a) The language of all strings in which both the number of a’s and the number of b’s
are even.
b) The language of all strings in which every a (if there are any) is followed
immediately by bb.
c) The language of all strings containing aba as substrings.

(a) Design DFA for the following over ∑={a,b}

i. All strings having odd number of b’s and ends with a.
ii. All strings containing the substring bb.

Unit -1
25 (b) Represent the following sets by regular expressions:
Difficult
(i) {⋀,111, 111111, 111111111…..}
(ii) The set of all strings over {a, b} beginning and ending with b.
(iii) The set of all strings over {0, 1} which has at least one zero.

 Identify type of strings in the following languages and give corresponding the regular
expression representing the set.
Unit -1
26
Difficult
  Find the language represented by the following regular expressions

Unit -1
27
Difficult

 Represent the following sets by regular expressions

Unit -1
28
Difficult

Study the automaton M (considering as initial state) given below and state whether the
Statements a)-e) are true or false with proper justification:

Unit -1
29
Difficult

a) M is a nondeterministic automaton.
b) 0100111 is accepted by M.
c) 010101010 is not accepted by M.

d)
e) A string having an even number of 0's is accepted by M.
 Construct the transition diagram corresponding to the regular expressions

Unit -1 (a) (ab+c*)*b

30
Difficult (b) a+bb+bab*a

 The set of Regular languages are closed under following operations

a) Union
b) Concatenation
c) Kleene *
Unit -2 d) Kleene +
31
Average e) Intersection
f) Difference
g) Complement

Justify with suitable example.

a) Formally define Grammar by 4 tuples

b) Describe correlation between grammar(G) and language generated by grammar (L(G))
Unit -2
32 by suitable example.
Average
c) Differentiate between Chomsky Normal Form and Griebach Normal Form
 Differentiate between ambiguous and unambiguous grammars and prove that following
grammars are ambiguous

Unit -2
33 a) E->E+E/E*E/(E)/id
Average
b) S->SS/(S)/a/∧

Find a reduced grammar equivalent to the grammar G by removing useless symbols whose
Unit -2 productions are
34
Average

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

Unit -2
35
Average

State rules to remove null-productions from CFG. Consider the grammar G whose productions
are
Unit -2
36
Average
Remove null Productions from this given grammar

37 Unit -2 State Rules to remove unit productions. Consider the grammar G whose productions are
Average
Eliminate unit productions and get an equivalent grammar.
 Formally define Moore and Mealy Machine and explain difference in output functions of two
Unit -2
38 machines by suitable example.
Average

Give Rules for converting Context Free grammar into Chomsky Normal Form Grammar(CNF).
Also, convert the given grammar into CNF.
Unit -2
39
Average

Unit -2
40
Average

In each case below, find a context-free grammar with no null-productions that generates the
same language, except possibly for null, as the given CFG

Unit -2
41
Difficult

42 Unit -2
Difficult

a) Illustrate Regular languages with example

 b) By making use of closure properties of regular Languages prove that if L is regular the
complement of L is also regular. Prove your point with suitable DFA example.
c) How can you prove that given language is not regular by Pumping lemma? Write down
proper steps.

 Discuss Myhill-Nerode Theorem for minimizing the DFA given below

Unit -2
43
Difficult

Identify Variables/Non-terminals and terminals in the given grammar

Unit -2
44
Difficult
Also, Find a grammar in CNF equivalent to this grammar

 Construct a grammar in Greibach normal form equivalent to the grammar

Unit -2
45
Difficult

46 Unit -2  Using the pumping lemma, show that the following sets are not regular
Difficult
 Unit -2  
47
Difficult

Unit -2  Gives Rules to convert CFG to GNF. Explain with suitable example.
48
Difficult

Unit -2
49  
Difficult

Unit -2  Show that set of palindromes is not regular language using pumping lemma.
50
Difficult

Unit -2
51
Difficult  

Unit -2
52  
Difficult

53 Unit -2  Construct a minimum state automaton equivalent to the DFA described as

Difficult
  Construct the minimum state automaton equivalent to the transition diagram

Unit -2
54
Difficult

55 Unit -2  Construct a minimum state automaton equivalent to the finite automaton described by
Difficult
 Consider a Mealy machine

Unit -2
56
Difficult

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

57 Unit -2 Consider the Moore machine described by the transition table given by Table. Find Output for
Difficult input string 001 and Construct the corresponding Mealy machine
  Consider the Mealy machine described below. Construct a Moore machine

Unit -2
58
Difficult

 Give steps to convert Moore to Mealy Machine and construct a Mealy Machine which is
equivalent to the Moore machine given by Table

Unit -2
59
Difficult

60 Unit -2 Consider the Moore machine described by the transition table given by Table.
Difficult
 a) Draw equivalent transition diagram from given table
b) Construct the corresponding Mealy machine represent it by transition table and
transition diagram

Unit -3  Design a Turing Machine over {a,b} accepting {a, b}* {aba} {a, b}*
61
Average

Unit -3 A DFA can remember a finite amount of information, but a PDA can remember an infinite
62
Average amount of information. Justify your answer with suitable example.

Draw the block diagram of Turing machine and reflect each of its components taking suitable
Unit -3
63 example
Average

FA does not and PDA accepts the given expression:

Unit -3 {L= an bn | n >=1}.
64
Average Comment by taking suitable example.

65 Unit -3 Construct PDA which accepts language

Average
 L={wcwr |w∊{a,b}+}

Unit -3  Draw the block diagram of Push Down Automaton and reflect each of its components taking
66
Average suitable example

Construct PDA which accepts language

Unit -3
67
Average
L={ancmbn |n,m>=1}

Unit -3  Construct PDA which accepts all strings with equal number of a’s and b’s
68
Average

Unit -3
69 Construct PDA which accepts all strings with number of a’s greater than number of b’s.
Average

Unit -3 Draw a neat and clean diagram and explain in detail correlation between languages and
70
Average grammars in Chomsky Hierarchy.

Unit -3  Design a turing machine accepting set of palindromes.

71
Difficult

Unit -3  Design a PDA for accepting a language {L= | n >=1}

72
Difficult
 Unit -3 Give an example of Context Free language that is not regular, also design Push Down
73
Difficult Automaton accepting the language.

Unit -3 Discuss about Non-deterministic Push Down Automaton with suitable example.
74
Difficult

Unit -3 Give tuples of Deterministic Push Down Automaton and explain with suitable example.
75
Difficult

Discuss about PDA acceptance with suitable example

Unit -3
76
Difficult
i. From empty Stack to final state.
ii. From Final state to Empty Stack

 Differentiate between following

Unit -3 a) DFA and PDA

77
Difficult b) PDA and Turing Machines
  Construct PDA which accepts language
Unit -3
78
Difficult
L={anb2n|w∊{a,b}+}

Unit -3  Construct PDA which accepts language

79
Difficult L={anb3n|w∊{a,b}+}

Unit -3   Design a TM to accept the language LE={a n b n cn | n >= 1 }

80
Difficult

Unit -3 Give tuples of Turing Machines and explain with suitable example.
81
Difficult

 Construct PDA which accepts all strings with number of a’s less than number of b’s.
Unit -3
82
Difficult

Unit -3  Discuss classification of Machines and language accepted by these machines given by Chomsky.
83
Difficult

Unit -3  Design a Turing Machine to accept the language L={0 n 1n/n>=1}

84
Difficult

85 Unit -3 Find the highest type number which can be applied to the following
Difficult productions:
  

Unit -3  Construct a Turing Machine that recognizes the language {wcw / w ∈{a, b} +}
86
Difficult

 Formally define following grammars with suitable examples. Also name the language generated
by these grammars.

Unit -3
87 a) Context sensitive grammars
Difficult
b) Unrestricted grammars

Differentiate between following

Unit -3
88
Difficult
a) Recursive and Recursively Enumerable languages.
b) Deterministic and Non-deterministic PDA
c) Deterministic and Non-deterministic Turing Machines

Unit -3
89
Difficult  Design a turing machine accepting {ss| s∊ {a, b}*}
 Unit -3 Construct PDA which accepts language
90
Difficult L={wwr |w∊{a,b}+}