NARULAINSTITUTEOFTECHNOLOGY
An Autonomous Institute under MAKAUT
B.TECH/CSE/EVEN/4th SEM/R_18/CS403/2021-2022
YEAR: 2022
FORMAL LANGUAGE AND AUTOMATA THEORY
CS403
TIME ALLOTTED: 3 HOURS FULL MARK S: 70
The figures in the margin indicate full marks.
Candidates are required to give their answers in their own words as far as practicable
GROUP – A
(Multiple Choice Type Questions)
1. Answer any ten from the following, choosing the correct alternative of each question: 10×1=10
SL. NO. Question Mar CO
ks
(i) Which of the following is Greibach Normal form? 1 CO1
a) A → aBC
b) A → BC
c) A → ab
d) A → abB
(ii) The Regular Expression representing the set of all strings over Σ={0,1} 1 CO2
starting with 0 and ending with 01 is
a) 0*(0+1)*01
b) 0(0+1)*01
c) 001(0+1)*
d) (0+1)*001
(iii) If P and Q are regular expressions (P is not null) then R = Q+RP has
unique solution as
a) R=Q*P
b) R=PQ*
c) R=Q*P*
d) R=QP*
(iv) The set of all strings over the alphabet S = {a, b} (including ε) is denoted 1 CO3
by
a) (a + b)*
b) (a + b)+
c) a+b+
d) a*b*
(v) A finite automata recognizes
a) any language
b) Context sensitive language
c) Context free language
d) Regular language.
(vi) Which of the following statement is TRUE? 1 CO2
a) Merger graph is a directed graph
b) Compatibility graph is a directed graph
c) Both merger graph and compatibility graph are directed graphs
d) Neither merger graph nor compatibility graph is directed
Page 1 of 4
Even semester theory examination 2022 under autonomy 28-JUNE-2022
NARULAINSTITUTEOFTECHNOLOGY
An Autonomous Institute under MAKAUT
(vii) Type 0 is accepted by 1 CO3
a) Linear bounded Automata
b) Push down automata
c) Finite state automata
d) Turing machine
(viii) Which is NOT a part of the mechanical diagram of 'Turing Machine'? 1 CO3
a) Input tape
b) read-write head
c) Finite Control
d) Stack
(ix) Maximum no of states of a DFA converted from a NFA with n states is 1 CO3
a) n
b) n2
c) 2n
d) None of these
(x) The class of regular language is NOT closed under 1 CO4
a) concatenation
b) union
c) Kleene closure
d) subset
(xi) The string 1101 does not belong to the set represented by 1 CO3
a) 110*(0+1)
b) 1(0+1)*101
c) (10)*(01)*(00+11)*
d) (00+(11)*01)*
(xii) Which one of the following statements is false?
a) L1 ∩ L2 is a CFL
b) L1 Ų L2 is a CFL
c) L1 Ų L2 is inherently ambiguous
d) L1 ∩ L2 is a CSL
GROUP – B
(Short Answer Type Questions)
Answer any three from the following: 3×5=15
SL. NO. Mar CO
ks
2. (a) Construct a CFG for palindrome for binary numbers. 2 CO4
(b) Construct a CFG for L = {0i 1j 2k | i = j or j = k} 3 CO4
3. (a) Differentiate between Mealy machine and Moore machine. 2 CO3
(b) Design a Finite Automata (FA) that accepts set of all strings over Σ = {a,b} 3 CO3
such that every string ends with abb.
4. (a) Construct a Finite Automata equivalent to the Regular Expression 3 CO3
L = ab(a+b)(ab)*b
Page 2 of 4
Even semester theory examination 2022 under autonomy 28-JUNE-2022
NARULAINSTITUTEOFTECHNOLOGY
An Autonomous Institute under MAKAUT
(b) Give regular expression that accepts set of all strings over ∑ = {0, 1} such 2 CO3
that number of 1’s is divisible by 3.Convert the given mealy machine into
an equivalent moore machine
5. 5 CO3
Convert the given mealy machine into an equivalent moore machine
6. Convert the following Context-free grammar into an equivalent 5
grammar in CNF
S → 1A /0B
A → 1AA /0S /0
B → 0BB /1S /1
GROUP – C
(Long Answer Type Questions)
Answer any three from the following: 3×15=45
SL. NO. Mar CO
ks No.
7. (a) Define PDA. Differentiate between PDA and NPDA. 3 CO1
(b) Design a PDA for the language 8 CO1
(c) Write down the chomsky classification of grammar. 4 CO1
8. (a) What do you mean by Distinguishable and Indistinguishable states ? 5
(b) Present State Next State, Output 10
Input = 0 Input = 1
AE, 0 B, 0
B F, 0 A, 0
C E, - C, 0
D F, 1 D, 0
E C, 1 C, 0
F D, - B, 0
Draw the Merger graph, Merger table, Compatibility graph then minimize
the above problem :-
9. (a) Define Pushdown Automata. 5
(b) Construct NDPA that accepts the language generated by the production S - 10
-> aSa | bSb | c. Show an instance description of this string abcba for this
problem.
10 (a) Prove that the language L = { 0n 1n 2n } | n >= 0} is not a CFL. 7
.
(b) Consider the following grammar and prove that it is an ambiguous 5 CO3
grammar.
E → E + E / E x E / id
(c) Construct a derivation tree for the string aabbabba for the CFG given by, 3 CO3
S → aB | bA
Page 3 of 4
Even semester theory examination 2022 under autonomy 28-JUNE-2022
NARULAINSTITUTEOFTECHNOLOGY
An Autonomous Institute under MAKAUT
A → a | aS | bAA
B → b | bS | Abb
11 (a) Differentiate between DFA and NFA 2 CO5
.
(b) Construct DFA equivalent to following corresponding NFA. 5 CO4
q0 q2
q1 q3
(c) Determine whether the following machine is lossless or lossy. If it is 8 CO5
lossless of finite order, determine its order. If it is lossy, find a shortest
output sequence produced by two different input sequences with the same
initial and final states.
PS NS, z
x=0 x=1
A A,1 C,1
B E,0 B,1
C D,0 A,0
D C,0 B,0
E B,1 A,0
Page 4 of 4
Even semester theory examination 2022 under autonomy 28-JUNE-2022
