ToC

MEGA QUIZ MERGED….

1. Assume R is a relation on a set A, aRb is partially ordered such that a and b are
_____________
a) reflexive
b) transitive
c) symmetric
d) reflexive and transitive

2. The non-Kleene Star operation accepts the following strings of finite length over set A =
{0,1}, where string s contains even number of 0 and 1
a) 01, 0011, 010101
b) 0011, 11001100
c) ε, 0011, 11001100
d) ε, 0011, 11001100

3. A regular language over an alphabet ∑ is one that cannot be obtained from the basic
languages using the operation
a) Union
b) Concatenation
c) Kleene*
d) All of the mentioned

4. Statement 1: A Finite automata can be represented graphically; Statement 2: The nodes can
be its states; Statement 3: The edges or arcs can be used for transitions. Which of the
following is correct?
a) Statement 1 is false but Statement 2 and 3 are correct
b) Statement 1 and 2 are correct while 3 is wrong
c) None of the mentioned statements are correct
d) All of the mentioned

5. The minimum number of states required to recognize an octal number divisible by 3 is:
a) 1
b) 3
c) 5
d) 7

6. Which of the following is not part of a 5-tuple finite automaton?

a) Input alphabet
b) Transition function
c) Initial State
d) Output Alphabet

7. If an infinite language is passed to Machine M, the subsidiary which gives a finite solution to
the infinite input tape is:
a) Compiler
 b) Interpreter
c) Loader and Linkers
d) None of the mentioned

8. The number of elements in the set for the Language L = {x ∈ (∑r)* | length of x is at most 2}
and ∑ = {0,1} is:
a) 7
b) 6
c) 8
d) 5

9. For the following change of state in FA, which of the following codes is an incorrect option?
a) δ(m, 1) = n
b) δ(0, n) = m
c) δ(m, 0) = ε
d) s: accept = false; cin >> char; if char = "0" goto n;

10. Given: ∑ = {a, b}

L = {x ∈ ∑* | x is a string combination}
∑^4 represents which among the following?
a) {aa, ab, ba, bb}
b) {aaaa, abab, ε, abaa, aabb}
c) {aaa, aab, aba, bbb}
d) All of the mentioned

1. Moore Machine is an application of:

a) Finite automata without input
b) Finite automata with output
c) Non Finite automata with output
d) None of the mentioned
2. In Moore machine, output is produced over the change of:
a) transitions
b) states
c) all of the mentioned
d) none of the mentioned
3. For a given Moore Machine, Given Input = ‘101010’, the output would be of length:
a) |Input| + 1
b) |Input|
c) |Input| - 1
d) Cannot be predicted
4. Statement 1: Null string is accepted in Moore Machine.
Statement 2: There are more than 5-Tuples in the definition of Moore Machine.
Choose the correct option:
a) Statement 1 is true and Statement 2 is true
b) Statement 1 is true while Statement 2 is false
c) Statement 1 is false while Statement 2 is true
d) Statement 1 and Statement 2, both are false
5. The total number of states and transitions required to form a Moore machine that will
produce residue mod 3 is:
a) 3 and 6
 b) 3 and 5
c) 2 and 4
d) 2 and 5
6. Complete the given table according to the given Moore machine.
The table represents Q0, Q2, 0 to the given Moore machine

Present State Next State 0 Next State 1 Output

Q0 Q1 Q2 1
Q1 Q2 Q0 1
Q2 Q0 Q1 0

The correct option is:

a) Q0, Q2, 0
b) Q0, Q2, 1
c) Q1, Q2, 1
d) Q1, Q0, 0

7. What is the output for the given language?

Language: A set of strings over ∑= {a, b} is taken as input and it prints 1 as an output
“for every occurrence of a, b as its substring.” (INPUT: abaaab)
a) 0010001
b) 0101010
c) 0111010
d) 0010000
8. The output alphabet can be represented as:
a) δ
b) ∆ (correct)
c) ∑
d) None of the mentioned
9. The output of Moore machine can be represented in the following format:
a) Op(t) = δ(Op(t))
b) Op(t) = δ(Op(t)i(t))
c) Op(t): ∑
d) None of the mentioned
10. Which of the following is a correct statement?
a) Moore machine has no accepting states
b) Mealy machine has accepting states
c) We can convert Mealy to Moore but not vice versa
d) All of the mentioned
11. • In Mealy machine, the output depends upon?
a) State
b) Previous State
c) State and Input
d) Only Input
12. • Which of the given are correct?
a) Moore machine has 6-tuples
b) Mealy machine has 6-tuples
c) Both Mealy and Moore have 6-tuples
d) None of the mentioned
13. • The following Mealy machine outputs which of the following?

a) 9’s Complement
b) 2’s Complement
c) 1’s Complement
d) 10’s Complement

14. • The output of Mealy machine can be represented in the following format:
a) Op(t) = δ(Op(t))
b) Op(t) = δ(Op(t) i(t))
c) Op(t): ∑
d) None of the mentioned
15. • The ratio of number of inputs to the number of outputs in a Mealy machine can be
given as:
a) 1
b) n : n+1
c) n+1 : n
d) none of the mentioned
16. • Mealy and Moore machines can be categorized as:
a) Inducers
b) Transducers
c) Turing Machines
d) Linearly Bounded Automata
17. • The major difference between Mealy and Moore machine is about:
a) Output Variations
b) Input Variations
c) All of the mentioned
d) None of the mentioned
18. • Statement 1: Mealy machine reacts faster to inputs.
Statement 2: Moore machine has more circuit delays.
Choose the correct option:
a) Statement 1 is true and Statement 2 is true
b) Statement 1 is true but Statement 2 is false
c) Statement 1 is false and Statement 2 is true
d) None of the mentioned is true
19. • Which of the following does the given Mealy machine represent?

a) 9’s Complement
b) 2’s Complement
c) 1’s Complement
d) 10’s Complement

20. • Which one of the following is true? A Mealy machine:

a) Produces a language
b) Produces a grammar
c) Can be converted to NFA
d) Has less circuit delays
21. • Which of the following does not belong to the input alphabet if S = {a, b}* for any
language?
a) a
b) b
c) ε
d) none of the mentioned
22. • The number of final states needed as per the given language?
Language L: {a^n | n is even or divisible by 3}
a) 1
b) 2
c) 3
d) 4
23. • An ε-NFA is ___________ in representation.
a) Quadruple
b) Quintuple
c) Triple
d) None of the mentioned
24. • State true or false: Both NFA and ε-NFA recognize exactly the same languages.
a) true
b) false
25. • Design an NFA for the language:
L: {a^n | n is even or divisible by 3}
Which of the following methods can be used to simulate the same?
a) ε-NFA
b) Power Construction Method
 c) Both ε-NFA and Power Construction Method
d) None of the mentioned
26. • Which of the following belongs to the epsilon closure set of a?
The epsilon closure of the set q is the set that contains q

a) {f1, f2, f3}

b) {a, f1, f2, f3}
c) {f1, f2}
d) none of the mentioned

27. • The number of elements present in the ε-closure(f2) in the given diagram:
The epsilon closure set of f2 consists of the elements: {f2, f3}

a) 0
b) 1
c) 2
d) 3
28. • Which of the steps are non-useful while eliminating the ε-transitions for the given
diagram?
The given are all steps followed while eliminating epsilon transitions from an NFA

a) Make a as accepting state of N’ if ECLOSE(p) contains an accepting state of N

b) Add an arc a to f1 labelled a if there is an arc labelled a in N from some state in
ECLOSE(a) to f1
c) Delete all arcs labelled as ε
d) None of the mentioned

29. • Is the language preserved in all the steps while eliminating epsilon transitions from
an NFA?
a) yes
b) no
30. • Remove all the epsilon transitions in the given diagram and compute the number of
a-transitions in the result?
The number of a-transitions in the result is 7

a) 5
b) 7
c) 9
d) 6
31. • Which of the following is not an example of Bounded Information?
a) fan switch outputs {on, off}
b) electricity meter reading
c) colour of the traffic light at the moment
d) none of the mentioned
32. • A language for which no DFA exists is a __________
a) Regular Language
b) Non-Regular Language
c) May be Regular
d) Cannot be said
33. • A DFA cannot be represented in the following format:
a) Transition graph
b) Transition Table
c) C code
d) None of the mentioned
34. • What does the following DFA accept?

Strings such that it ends with ‘101’ accepted by DFA

a) x is a string such that it ends with ‘101’
b) x is a string such that it ends with ‘01’
c) x is a string such that it has odd 1’s and even 0’s
d) x is a string such that it has starting and ending character as 1

35. • When are 2 finite states equivalent?

a) Same number of transitions

b) Same number of states
c) Same number of states as well as transitions
d) Both are final states
36. • What does the following figure most correctly represent?

The figure represents the initial as well as the final state with an iteration of x
a) Final state with loop x
b) Transitional state with loop x
c) Initial state as well as final state with loop x
d) Insufficient Data

37. • Which of the following will not be accepted by the following DFA?
ababaabaa is not accepted by DFA

a) ababaabaa
b) abbbaa
c) abbbaabb
d) abbaabbaa
38. • Which of the following will the given DFA not accept?
Epsilon is acceptance state which DFA won’t accept

a) ε
b) 11010
c) 10001010
d) String of letter count 11

39. • Can a DFA recognize a palindrome number?

a) Yes
b) No
c) Yes, with input alphabet as ∑*
d) Can’t be determined
40. • Which of the following is not an example of finite state machine system?
a) Control Mechanism of an elevator
b) Combinational Locks
c) Traffic Lights
d) Digital Watches
41. • The password to the admin's account = "administrator". The total number of states
required to make a password-pass system using DFA would be __________
a) 14 states
b) 13 states
c) 12 states
d) A password pass system cannot be created using DFA
42. • Which of the following is the corresponding language to the given DFA?
The corresponding language ends in 1 & does not contain substring 00 for the given
DFA
 a) L = {x ∈ {0, 1}* | x ends in 1 and does not contain substring 01}
b) L = {x ∈ {0,1} | x ends in 1 and does not contain substring 00}*
c) L = {x ∈ {0,1} | x ends in 1 and does not contain substring 00}
d) L = {x ∈ {0,1}* | x ends in 1 and does not contain substring 11}

43. • Let ∑ = {a, b, ..., z} and A = {Hello, World}, B = {Input, Output}, then (A* ∩ B)
∪ (B* ∩ A) can be represented as:
a) {Hello, World, Input, Output, ε}
b) {Hello, World, ε}
c) {Input, Output, ε}
d) {}
44. • Let the given DFA consist of x states. Find x - y such that y is the number of states
on minimization of DFA?

a) 3
b) 2
c) 1
d) 4
45. • For a machine to surpass all the letters of the alphabet excluding vowels, how many
number of states in DFA would be required?
a) 3
b) 2
c) 22
d) 27

46. • For the DFA given below compute the following:

Union of all possible combinations at state 7, 8 and 9.

a) {aba, ac, cc, ca, cb, bc, bab, ca}

b) {bab, bc, ac, aba, ca, aac, ccb}
c) {cc, ca, cb, aba, bab, ac}
d) {aba, ac, cc, ca, cb, bc, bab, caa}

47. • Given L = {x ∈ ∑* = {a, b} | x has equal number of a’s and b’s}.

Which of the following properties satisfy the regularity of the given language?
a) Regularity is dependent upon the length of the string
b) Regularity is not dependent upon the length of the string
c) Can’t be said for a particular string of a language
d) It may depend on the length of the string
48. • Given:
L = {x ∈ ∑ = {0,1} | x = 0^n 1^n for n ≥ 1}; Can there be a DFA possible for the
language?
a) Yes
b) No
49. • δ(A, 1) = B, δ(A, 0) = A
δ(B, (0,1)) = C
δ(C, 0) = A (Initial state = A)
String = "011001" is transit at which of the states?
a) A
b) C
c) B
d) Invalid String
50. • Given Language: L = {x ∈ ∑ = {a, b} | x has a substring ‘aa’ in the production}.
Which of the corresponding representations notate the same?

a) L = {a, b} | x has a substring ‘aa’ in the production - option a

b) L = {a, b} | x has a substring ‘aa’ in the production - option b
c) L = {a, b} | x has a substring ‘aa’ in the production - option c
d) L = {a, b} | x has a substring ‘aa’ in the production - option d

51. • Let u = ‘1101’, v = ‘0001’, then uv = 11010001 and vu = 00011101. Using the
given information what is the identity element for the string?
a) u⁻¹
b) v⁻¹
c) u⁻¹ v⁻¹
d) ε

52. • Which of the following substrings will the given notation result?
The given DFA notation accepts strings of even length & prefix ‘01’

a) 0101011
b) 0101010
c) 010100
d) 100001
53. • Predict the following step in the given bunch of steps which accepts strings of even
length and has prefix = ‘01’
δ(q0, ε) = q0 < δ(q0, 0) = δ(δ(q0, ε), 0) = δ(q0, 0) = q1 < _______________
a) δ(q0, 011) = δ(δ(q0, 1), 1) = δ(q2, 1) = q3
b) δ(q0, 01) = δ(δ(q0, 0), 1) = δ(q1, 1) = q2
c) δ(q0, 011) = δ(δ(q01, 1), 1) = δ(q2, 0) = q3
d) δ(q0, 0111) = δ(δ(q0, 011), 0) = δ(q3, 1) = q2
54. • Fill the missing blank in the given Transition Table:
Language L = {x ∈ ∑ = {0,1} | x accepts all binary strings not divisible by 3}
The tabular representation of DFA is Q1

a) Q0
b) Q1
c) Q2
d) No Transition

55. • Which among the following is the missing transition in the given DFA?
L = {x ∈ ∑ = {a, b} | x starts with a and ends with b}
Find the missing transition in the given DFA
 a) δ(q0, a) = q0
b) δ(F, a) = q1
c) δ(F, a) = D
d) δ(q1, a) = D

56. • The complement of a language will only be defined when and only when the
__________ over the language is defined.
a) String
b) Word
c) Alphabet
d) Grammar
57. • Which among the following is not notated as infinite language?
a) Palindrome
b) Reverse
c) Factorial
d) L = {ab}*
58. • Which among the following states would be notated as the final state/acceptance
state?
L = {x ∈ ∑ = {a, b} | length of x is 2}
The final state/acceptance state is q2 to the given language

a) q1
b) q2
c) q1, q2
d) q3

59. • Which of the following are the final states in the given DFA according to the
Language given?
L = {x ∈ ∑ = {a, b} | length of x is at most 2}
The final state/acceptance state is q0, q1, q2 to the given language
 a) q0, q1
b) q0, q2
c) q1, q2
d) q0, q1, q2

60. • How many languages are over the alphabet R?

a) countably infinite
b) countably finite
c) uncountable finite
d) uncountable infinite
61. • According to the 5-tuple representation i.e. FA = {Q, ∑, δ, q, F}
Statement 1: q ∈ Q’; Statement 2: F ∈ Q
a) Statement 1 is true, Statement 2 is false
b) Statement 1 is false, Statement 2 is true
c) Statement 1 is false, Statement 2 may be true
d) Statement 1 may be true, Statement 2 is false
62. • δˆ tells us the best:
a) how the DFA S behaves on a word u
b) the state is the dumping state
c) the final state has been reached
d) Kleene operation is performed on the set
63. • Which of the following option is correct?
A = {{abc, aaba}, {ε, a, bb}}
a) abcbb ∉ A
b) ε ∈ A
c) ε may not belong to A
d) abca ∉ A
64. • For a DFA accepting binary numbers whose decimal equivalent is divisible by 4,
what are all the possible remainders?
a) 0
b) 0, 2
c) 0, 2, 4
d) 0, 1, 2, 3
65. • Which of the following x is accepted by the given DFA (x is a binary string ∑ =
{0,1})?
The given DFA accepts all binary strings that are divisible by 3 & 2
 a) divisible by 3
b) divisible by 2
c) divisible by 2 and 3
d) divisible by 3 and 2

66. • Given:
L1 = {x ∈ ∑* | x contains even no’s of 0’s}
L2 = {x ∈ ∑* | x contains odd no’s of 1’s}
Number of final states in Language L1 U L2?
a) 1
b) 2
c) 3
d) 4
67. • The maximum number of transitions which can be performed over a state in a
DFA?
∑ = {a, b, c}
a) 1
b) 2
c) 3
d) 4
68. • The maximum sum of in-degree and out-degree over a state in a DFA can be
determined as:
∑ = {a, b, c, d}
a) 4 + 4
b) 4 + 16
c) 4 + 0
d) depends on the Language
69. • The sum of minimum and maximum number of final states for a DFA with n states
is equal to:
a) n + 1
b) n
c) n - 1
d) n + 2
70. • There are ________ tuples in a finite state machine.
a) 4
b) 5
c) 6
d) unlimited
71. • Transition function maps:
a) Σ * Q -> Σ
b) Q * Q -> Σ
c) Σ * Σ -> Q
d) Q * Σ -> Q
72. • Number of states required to accept string ending with 10:
a) 3
b) 2
c) 1
d) can’t be represented
73. • Extended transition function is:
a) Q * Σ -> Q*
b) Q * Σ -> Q
c) Q* * Σ* -> Σ
d) Q * Σ -> Σ
74. • δ*(q, ya) is equivalent to:
a) δ((q, y), a)
b) δ(δ(q, y), a)*
c) δ(q, ya)
d) independent from δ notation
75. • String X is accepted by finite automata if:
a) δ*(q, x) ∈ A
b) δ(q, x) ∈ A
c) δ(Q0, x) ∈ A*
d) δ(Q0, x) ∈ A
76. • Languages of an automata is:
a) If it is accepted by automata
b) If it halts
c) If automata touch final state in its lifetime
d) All languages are languages of automata
77. • Language of finite automata is:
a) Type 0
b) Type 1
c) Type 2
d) Type 3
78. • Finite automata requires minimum _______ number of stacks.
a) 1
b) 0
c) 2
d) None of the mentioned
79. • Number of final states required to accept Φ in minimal finite automata:
a) 1
b) 2
c) 3
d) None of the mentioned
80. • Regular expression for all strings that start with "ab" and end with "bba" is:
a) ababbba
b) ab(ab)*bba
*c) ab(a+b)bba
d) All of the mentioned
81. • How many DFA’s exist with two states over input alphabet {0,1}?
a) 16
b) 26
c) 32
d) 64
82. • The basic limitation of finite automata is that:
a) It can’t remember an arbitrarily large amount of information.
b) It sometimes recognizes grammars that are not regular.
c) It sometimes fails to recognize regular grammars.
d) All of the mentioned
83. • Number of states required to simulate a computer with memory capable of storing
‘3’ words each of length ‘8’:
a) 3 * 28
b) 2^(3*8)
c) 2^(3+8)
d) None of the mentioned
84. • FSM with output capability can be used to add two given integers in binary
representation. This is:
a) True
b) False
c) May be true
d) None of the mentioned
85. • Which of the following options is correct?
Statement 1: Initial State of NFA is Initial State of DFA.
Statement 2: The final state of DFA will be every combination of final state of NFA.
a) Statement 1 is true and Statement 2 is true
b) Statement 1 is true and Statement 2 is false
c) Statement 1 can be true and Statement 2 is true
d) Statement 1 is false and Statement 2 is also false
86. • Given Language: L = {ab U aba}*
If X is the minimum number of states for a DFA and Y is the number of states to
construct the NFA,
|X - Y| = ?
a) 2
b) 3
c) 4
d) 1
87. • An automaton that presents output based on previous state or current input:
a) Acceptor
b) Classifier
c) Transducer
d) None of the mentioned
88. • If NFA of 6 states excluding the initial state is converted into DFA, maximum
possible number of states for the DFA is?
a) 64
b) 32
c) 128
d) 127
89. • NFA, in its name has ’non-deterministic’ because of:
a) The result is undetermined
b) The choice of path is non-deterministic
c) The state to be transited next is non-deterministic
d) All of the mentioned
90. • Which of the following is correct proposition?
Statement 1: Non determinism is a generalization of Determinism.
Statement 2: Every DFA is automatically an NFA
a) Statement 1 is correct because Statement 2 is correct
b) Statement 2 is correct because Statement 2 is correct
c) Statement 2 is false and Statement 1 is false
d) Statement 1 is false because Statement 2 is false
91. • Given Language L = {x ∈ {a, b}* | x contains aba as its substring}
Find the difference of transitions made in constructing a DFA and an equivalent
NFA?
a) 2
b) 3
c) 4
d) Cannot be determined
92. • The construction time for DFA from an equivalent NFA (m number of nodes) is:
a) O(m^2)
b) O(2^m)
c) O(m)
d) O(log m)
93. • If n is the length of input string and m is the number of nodes, the running time of
DFA is x times that of NFA. Find x?
a) 1/m^2
b) 2^m
c) 1/m
d) log m
94. • Which of the following option is correct?
a) NFA is slower to process and its representation uses more memory than DFA
b) DFA is faster to process and its representation uses less memory than NFA
c) NFA is slower to process and its representation uses less memory than DFA
d) DFA is slower to process and its representation uses less memory than NFA
95. • The number of tuples in an extended Non-Deterministic Finite Automaton:
a) 5
b) 6
c) 7
d) 4
96. • Choose the correct option for the given statement:
Statement: The DFA shown represents all strings which have 1 at second last position.
The given figure is NFA with all strings which have 1 at second last position

a) Correct
b) Incorrect, Incomplete DFA
c) Wrong proposition
d) May be correct

97. • What is wrong in the given definition?

Def: ({q0, q1, q2}, {0,1}, δ, q3, {q3})
a) The definition does not satisfy 5 Tuple definition of NFA
b) There are no transition definitions
c) Initial and Final states do not belong to the Graph
d) Initial and final states can’t be same
98. • If δ is the transition function for a given NFA, then we define the δ’ for the DFA
accepting the same language would be:
Note: S is a subset of Q and a is a symbol.
a) δ’ (S, a) = ∪_{p∈S} δ (p, a)
b) δ’ (S, a) = ∪{p≠S} δ (p, a)
c) δ’ (S, a) = ∪{p∈S} δ(p)
d) δ’ (S) = ∪_{p≠S} δ(p)
99. • What is the relation between DFA and NFA on the basis of computational power?
a) DFA > NFA
b) NFA > DFA
c) Equal
d) Can’t be said
100. • If a string S is accepted by a finite state automaton, S = s1 s2 s3 … sn where
si ∈ ∑ and there exists a sequence of states r0, r1, r2 … rn such that δ(r(i), si+1) =
ri+1 for each 0, 1, … n-1, then r(n) is:
a) initial state
b) transition symbol
c) accepting state
d) intermediate state
101. • According to the given table, compute the number of transitions with 1 as
its symbol but not 0:

a) 4
b) 3
c) 2
d) 1

102. • From the given table, δ*(q0, 011) = ?

a) {q0}
b) {q1} ∪ {q0, q1, q2}
c) {q2, q1}
d) {q3, q1, q2, q0}
103. • Number of times the state q3 or q2 is being a part of extended 6 transition
state is:

a) 6
b) 5
c) 4
d) 7

104. • Predict the missing procedure:

The extended transition state implementation is {Q0, Q2}
i. Δ(Q0, ε) = {Q0}
ii. Δ(Q0, 01) = {Q0, Q1}
iii. δ(Q0, 010) = ?

a) {Q0, Q1, Q2}

b) {Q0, Q1}
c) {Q0, Q2}
d) {Q1, Q2}

105. Subset Construction method refers to:

a) Conversion of NFA to DFA
b) DFA minimization
c) Eliminating Null references
d) ε-NFA to NFA
106. Given Language:
Ln = {x ∈ {0,1}* | |x| ≥ n, nth symbol from the right in x is 1}
How many states are required to execute L3 using NFA?
a) 16
b) 15
c) 8
d) 7
107. Which of the following does the given NFA represent?
The given diagram represents {11, 110}{0}

a) {11, 101}{01}
b) {110, 01}{11}
**c) {11, 110}{0}**
d) {00, 110}*{1}

108. The number of transitions required to convert the following into equivalent
DFA:
The number of transitions required to convert is 2

a) 2
b) 3
c) 1
d) 0

109. If L is a regular language, Lc and Lr both will be:

a) Accepted by NFA
b) Rejected by NFA
 c) One of them will be accepted
d) Cannot be said
110. In NFA, this very state is like dead-end non-final state:
a) ACCEPT
b) REJECT
c) DISTINCT
d) START
111. We can represent one language in more than one FSMs, true or false?
a) TRUE
b) FALSE
c) May be true
d) Cannot be said
112. The production of form non-terminal -> ε is called:
a) Sigma Production
b) Null Production
c) Epsilon Production
d) All of the mentioned
113. Which of the following is a regular language?
a) String whose length is a sequence of prime numbers
b) String with substring wwr in between
c) Palindrome string
d) String with even number of zero’s
114. Which of the following recognizes the same formal language as of DFA and
NFA?
a) Power set Construction
b) Subset Construction
c) Robin-Scott Construction
d) All of the mentioned
115. Under which of the following operations is NFA not closed?
a) Negation
b) Kleene
c) Concatenation
d) None of the mentioned
116. It is less complex to prove the closure properties over regular languages using:
a) NFA
b) DFA
c) PDA
d) Can’t be said
117. Which of the following is an application of Finite Automaton?
a) Compiler Design
b) Grammar Parsers
c) Text Search
d) All of the mentioned
118. John is asked to make an automaton which accepts a given string for all the
occurrences of ‘1001’ in it. How many number of transitions would John use such
that the string processing application works?
a) 9
b) 11
c) 12
d) 15
119. Which of the following do we use to form an NFA from a regular expression?
a) Subset Construction Method
b) Power Set Construction Method
c) Thompson Construction Method
d) Scott Construction Method
120. Which among the following can be an example of application of finite state
machine (FSM)?
a) Communication Link
b) Adder
c) Stack
d) None of the mentioned
121. Which among the following is not an application of FSM?
a) Lexical Analyser
b) BOT
c) State charts
d) None of the mentioned
122. L1= {w | w does not contain the string "tr"}
L2 = {w | w does contain the string "tr"}
Given ∑ = {t, r}, the difference of the minimum number of states required to form L1
and L2 is?
a) 0
b) 1
c) 2
d) Cannot be said
123. Predict the number of transitions required to automate the following language
using only 3 states:
L = {w | w ends with 00}
a) 3
b) 2
c) 4
d) Cannot be said
124. The total number of states to build the given language using DFA:
L = {w | w has exactly 2 a’s and at least 2 b’s}
a) 10
b) 11
c) 12
d) 13
125. • Given Language: {x | x is divisible by 3}
The total number of final states to be assumed in order to accept the number
constituting {0, 1} is:
a) 0
b) 1
c) 2
d) 3
126. • A binary string is divisible by 4 if and only if it ends with:
a) 100
b) 1000
c) 1100
d) 0011
127. • Let L be a language whose FA consists of 5 acceptance states and 11 non-
final states. It further consists of a dumping state. Predict the number of acceptance
states in Lc.
a) 16
b) 11
c) 5
d) 6
128. • If L1 and L2 are regular languages, which among the following is an
exception?
a) L1 ∪ L2
b) L1 – L2
c) L1 ∩ L2
d) All of the mentioned
129. • Predict the analogous operation for the given language:
A: {[p, q] | p ∈ A1, q does not belong to A2}
a) A1 – A2
b) A2 – A1
c) A1 . A2
d) A1 + A2
130. • Which among the following NFA’s is correct corresponding to the given
Language?
L = {x ∈ {0, 1} | 3rd bit from right is 0}

a) NFA’s corresponding to given Language L = {{0, 1} | 3rd bit from right is 0} -

option a
b) NFA’s corresponding to given Language L = {{0, 1} | 3rd bit from right is 0} -
option b
c) NFA’s corresponding to given Language L = {{0, 1} | 3rd bit from right is 0} -
option c
d) None of the mentioned
131. • Statement 1: NFA computes the string along parallel paths.
Statement 2: An input can be accepted at more than one place in an NFA.
Which among the following options are most appropriate?
a) Statement 1 is true while 2 is not
b) Statement 1 is false while 2 is not
c) Statement 1 and 2, both are true
d) Statement 1 and 2, both are false
132. • Which of the following options is correct for the given statement?
Statement: If K is the number of states in NFA, the DFA simulating the same
language would have states less than 2^k.
a) True
b) False
133. • Let N(Q, ∑, δ, q0, A) be the NFA recognizing a language L. Then for a
DFA (Q’, ∑, δ’, q0’, A’), which among the following is true?
a) Q’ = P(Q)
b) Δ’ = δ’ (R, a) = {q ∈ Q | q ∈ δ (r, a), for some r ∈ R}
c) Q’ = {q0}
d) All of the mentioned
134. • There exists an initial state, 17 transition states, 7 final states and one
dumping state. Predict the maximum number of states in its equivalent DFA?
a) 226
b) 224
c) 225
d) 223
135. • Under which of the following operations is NFA not closed?
a) Negation
b) Kleene
c) Concatenation
d) None of the mentioned
136. • It is less complex to prove the closure properties over regular languages
using:
a) NFA
b) DFA
c) PDA
d) Can’t be said
137. • Which of the following is an application of Finite Automaton?
a) Compiler Design
b) Grammar Parsers
c) Text Search
d) All of the mentioned
138. • John is asked to make an automaton which accepts a given string for all the
occurrences of ‘1001’ in it. How many number of transitions would John use such
that the string processing application works?
a) 9
b) 11
c) 12
d) 15
139. • Which of the following do we use to form an NFA from a regular
expression?
 a) Subset Construction Method
b) Power Set Construction Method
c) Thompson Construction Method
d) Scott Construction Method
140. • Which among the following can be an example of application of finite state
machine (FSM)?
a) Communication Link
b) Adder
c) Stack
d) None of the mentioned
141. • Which among the following is not an application of FSM?
a) Lexical Analyser
b) BOT
c) State charts
d) None of the mentioned
142. • L1= {w | w does not contain the string "tr"}
L2= {w | w does contain the string "tr"}
Given ∑= {t, r}, the difference of the minimum number of states required to form L1
and L2 is?
a) 0
b) 1
c) 2
d) Cannot be said
143. • Predict the number of transitions required to automate the following
language using only 3 states:
L= {w | w ends with 00}
a) 3
b) 2
c) 4
d) Cannot be said
144. • The total number of states to build the given language using DFA:
L= {w | w has exactly 2 a’s and at least 2 b’s}
a) 10
b) 11
c) 12
d) 13
145. According to the given transitions, which among the following are the epsilon
closures of q1 for the given NFA?
Δ(q1, ε) = {q2, q3, q4}
Δ(q4, 1) = q1
Δ(q1, ε) = q1
a) q4
b) q2
c) q1
d) q1, q2, q3, q4
146. State true or false?
Statement: An NFA can be modified to allow transitions without input alphabets,
along with one or more transitions on input symbols.
a) True
b) False
147. State true or false?
Statement: ε (Input) does not appear on Input tape.
a) True
b) False
148. Statement 1: ε-transition can be called as hidden non-determinism.
Statement 2: δ(q, ε) = p means from q it can jump to p with a shift in read head.
Which among the following options is correct?
a) Statement 1 and 2, both are correct
b) Statement 1 and 2, both are wrong
c) Statement 1 is correct while Statement 2 is wrong
d) Statement 1 is wrong while Statement 2 is correct
149. ε-closure of q1 in the given transition graph:
a) {q1}
b) {q0, q2}
c) {q1, q2}
d) {q0, q1, q2}
150. Predict the total number of final states after removing the ε-moves from the
given NFA?
a) 1
b) 2
c) 3
d) 0
151. For NFA with ε-moves, which among the following is correct?
a) Δ: Q × (∑ ∪ {ε}) -> P(Q)
b) Δ: Q × (∑) -> P(Q)
c) Δ: Q × (∑*) -> P(Q)
d) All of the mentioned
152. Which among the following is false?
ε-closure of a subset S of Q is:
a) Every element of S ∈ Q
b) For any q ∈ ε(S), every element of δ(q, ε) is in ε(S)
c) No other element is in ε(S)
d) None of the mentioned
153. The automaton which allows transformation to a new state without consuming
any input symbols:
a) NFA
b) DFA
c) NFA-ε
d) All of the mentioned
154. ε-transitions are:
a) conditional
b) unconditional
c) input dependent
d) none of the mentioned
155. The __________ of a set of states, P, of an NFA is defined as the set of states
reachable from any state in P following ε-transitions.
a) ε-closure
b) ε-pack
c) Q in the tuple
d) None of the mentioned
156. The ε-NFA recognizable languages are not closed under:
a) Union
b) Negation
c) Kleene Closure
d) None of the mentioned
157. The automaton which allows transformation to a new state without consuming
any input symbols:
a) NFA
b) DFA
c) NFA-ε
d) All of the mentioned
158. ε-transitions are:
a) conditional
b) unconditional
c) input dependent
d) none of the mentioned
159. The __________ of a set of states, P, of an NFA is defined as the set of states
reachable from any state in P following ε-transitions.
a) ε-closure
b) ε-pack
c) Q in the tuple
d) None of the mentioned
160. The ε-NFA recognizable languages are not closed under ___________
a) Union
b) Negation
c) Kleene Closure
d) None of the mentioned
161. Is the language preserved in all the steps while eliminating epsilon transitions
from an NFA?
a) yes
b) no
162. An ε-NFA is ___________ in representation.
a) Quadruple
b) Quintuple
c) Triple
d) None of the mentioned
163. State true or false:
Statement: Both NFA and ε-NFA recognize exactly the same languages.
a) true
b) false
164. • Which of the following does not belong to the input alphabet if S = {a, b}*
for any language?
a) a
b) b
c) ε
d) none of the mentioned
165. • The number of final states we need as per the given language?
Language L: {a^n | n is even or divisible by 3}
a) 1
b) 2
c) 3
d) 4
166. • State true or false:
Statement: Both NFA and ε-NFA recognize exactly the same languages.
a) true
b) false
167. • Design an NFA for the language:
L: {a^n | n is even or divisible by 3}
Which of the following methods can be used to simulate the same?
a) ε-NFA
b) Power Construction Method
c) ε-NFA and Power Construction Method
d) None of the mentioned
168. • Which of the following belongs to the epsilon closure set of a?
The epsilon closure of the set q is the set that contains q

a) {f1, f2, f3}

b) {a, f1, f2, f3}
c) {f1, f2}
d) none of the mentioned
169. • The number of elements present in the ε-closure(f2) in the given diagram:
The number of elements present in the ε-closure(f2) is 2 in the given diagram

a) 0
b) 1
c) 2
d) 3
170. • Which of the steps are non-useful while eliminating the ε-transitions for the
given diagram?
The given are the steps followed while converting an ε-NFA to just NFA

a) Make a as accepting state of N’ if ECLOSE(p) contains an accepting state of N

b) Add an arc a to f1 labelled a if there is an arc labelled a in N from some state in
ECLOSE(a) to f1
c) Delete all arcs labelled as ε
d) None of the mentioned
171. • Remove all the epsilon transitions in the given diagram and compute the
number of a-transitions in the result?
The number of a-transitions in the result is 7

a) 5
b) 7
c) 9
d) 6
172. • Regular sets are closed under union, concatenation, and Kleene closure.
a) True
b) False
c) Depends on regular set
d) Can’t say
173. • Complement of a DFA can be obtained by:
a) making starting state as final state
b) no trivial method
c) making final states non-final and non-final to final
d) make final as a starting state
174. • Complement of regular sets are ___________
a) Regular
b) CFG
c) CSG
d) RE
175. • If L1 and L2 are regular sets then intersection of these two will be:
a) Regular
b) Non-Regular
c) Recursive
d) Non-Recursive
176. • If L1 is regular, L2 is unknown but L1 - L2 is regular, then L2 must be:
a) Empty set
b) CFG
c) Decidable
d) Regular
177. • Reverse of a DFA can be formed by:
a) using PDA
b) making final state as non-final
c) making final as starting state and starting state as final state
d) None of the mentioned
178. • Reverse of (0 + 1)* will be:
a) Phi
b) Null
*c) (0 + 1) **
d) (0 + 1)
179. • A ___________ is a substitution such that h(a) contains a string for each a.
a) Closure
b) Interchange
c) Homomorphism
d) Inverse Homomorphism
180. • Homomorphism of a regular set is _______
a) Universal set
b) Null set
c) Regular set
d) Non regular set
181. • (a^5 b^5)* is an example of ________
a) Type 0 language
b) Type 1 language
c) Type 2 language
d) Type 3 language
182. • Which of the following is a type 3 language?
a) Strings of 0’s whose length is perfect square
b) Palindrome string
c) Strings of 0’s having length prime number
d) String of odd number of 0’s
183. • a^n b^n where (n + m) is even.
a) Type 0
b) Type 1
c) Type 2
d) Type 3
184. • Complement of a^n b^m where n ≥ 4 and m ≤ 3 is example of:
a) Type 0
b) Type 1
c) Type 2
d) Type 3
185. • a^n b^m where n ≥ 1, m ≥ 1, nm ≥ 3 is example of:
a) Type 0
b) Type 1
c) Type 2
d) Type 3
186. • Complement of (a + b)* will be:
a) Φ (empty set)
b) null
c) a
d) b
187. • L is a regular language if and only if the set of __________ classes of IL is
finite.
a) Equivalence
b) Reflexive
c) Myhill
d) Nerode
188. • A language can be generated from simple primitive language in a simple
way if and only if
a) It is recognized by a device of infinite states
b) It takes no auxiliary memory
c) All of the mentioned
d) None of the mentioned
189. • Which of the following does not represent the given language?
Language: {0, 01}
a) 0 + 01
b) {0} U {01}
c) {0} U {0}{1}
d) {0} ^ {01}
190. • According to the given language, which among the following expressions
does it correspond to?
Language L = {x ∈ {0,1} | x is of length 4 or less}
a) (0 + 1 + 0 + 1 + 0 + 1 + 0 + 1)^4
b) (0 + 1)^4
c) (01)^4
d) (0 + 1 + ε)^4
191. • Which among the following looks similar to the given expression?
((0 + 1) . (0 + 1)) *
a) {x ∈ {0,1} | x is all binary numbers with even length}*
b) {x ∈ {0,1} | x is all binary numbers with even length}
c) {x ∈ {0,1}* | x is all binary numbers with odd length}
d) {x ∈ {0,1} | x is all binary numbers with odd length}
192. • If R represents a regular language, which of the following represents the
Venn-diagram most correctly?

The diagram represents the Venn-diagram of R*

a) An irregular set
b) R*
 c) R complement
d) R reverse
193. • The given NFA corresponds to which of the following regular expressions?
The given NFA corresponds to (0 + 1)* (00 + 11) (0 + 1)*

a) (0 + 1) (00 + 11) (0 + 1) **
b) (0 + 1)* (00 + 11)* (0 + 1)*
c) (0 + 1)* (00 + 11) (0 + 1)
d) (0 + 1) (00 + 11) (0 + 1)*
194. • Concatenation operation refers to which of the following set operations:
a) Union
b) Dot
c) Kleene
d) Two of the options are correct
195. • Concatenation of R with Φ outputs:
a) R
b) Φ
c) R.Φ
d) None of the mentioned
196. • RR* can be expressed in which of the forms:
a) R+
b) R-
c) R+ U R-
d) R
197. A finite automaton accepts which type of language:
a) Type 0
b) Type 1
c) Type 2
d) Type 3
198. Which among the following are incorrect regular identities?
a) εR = R
b) ε = ε*
c) Φ* = ε
d) RΦ = R
199. Simplify the following regular expression:
ε + 1* (011)* (1* (011))
a) (1 + 011)*
b) (1* (011))
**c) (1 + (011))***
d) (1011)*
200. P, O, R be regular expressions over ∑, P is not ε, then R = Q + RP has a
unique solution:
a) Q*P
b) QP*
c) QP
d) (PO)*
201. Arden’s theorem is true for:
a) More than one initial states
b) Null transitions
c) Non-null transitions
d) None of the mentioned
202. The difference between number of states with regular expression (a + b) and (a
+ b)* is:
a) 1
b) 2
c) 3
d) 0
203. In order to represent a regular expression, the first step to create the transition
diagram is:
a) Create the NFA using Null moves
b) Null moves are not acceptable, thus should not be used
c) Predict the number of states to be used in order to construct the Regular expression
d) None of the mentioned
204. (0 + ε)(1 + ε) represents:
a) {0, 1, 01, ε}
b) {0, 1, ε}
c) {0, 1, 01, 11, 00, 10, ε}
d) {0, 1}
205. The minimum number of states required to automate the following Regular
Expression:
(1)* (01 + 10) (1)*
a) 4
b) 3
c) 2
d) 5
206. Regular Expression denote precisely the ________ of Regular Language.
a) Class
b) Power Set
c) Super Set
d) None of the mentioned
207. • Which of the following is correct?
Statement 1: ε represents a single string in the set.
Statement 2: Φ represents the language that consists of no string.
a) Statement 1 and 2 both are correct
b) Statement 1 is false but 2 is correct
c) Statement 1 and 2 both are false
d) There is no difference between both the statements, ε and Φ are different notation
for same reason
208. • The appropriate precedence order of operations over a Regular Language is:
a) Kleene, Union, Concatenate
b) Kleene, Star, Union
c) Kleene, Dot, Union
d) Star, Union, Dot
209. • Regular Expression R and the language it describes can be represented as:
a) R, R(L)
b) L(R), R(L)
c) R, L(R)
d) All of the mentioned
210. • Let for ∑= {0,1} R = (∑∑∑)*, the language of R would be:
a) {w | w is a string of odd length}
b) {w | w is a string of length multiple of 3}
c) {w | w is a string of length 3}
d) All of the mentioned
211. • If ∑ = {0,1}, then Φ* will result to:
a) ε
b) Φ
c) ∑
d) None of the mentioned
212. • The given NFA represents which of the following NFA:
a) (ab U a)*
b) (ab U a*)
c) (ab U a*)
d) (ab) U a**
213. • Which of the following represents a language which has no pair of
consecutive 1’s if ∑= {0,1}?
a) (0 + 10)*(1 + ε)
b) (0 + 10)(1 + ε)
c) (0 + 101)(0 + ε)
d) (1 + 010)(1 + ε)
214. • The finite automata accept the following languages:
a) Context Free Languages
b) Context Sensitive Languages
c) Regular Languages
d) All the mentioned
215. • (a + bc) most correctly represents:
a) (a + b)c
b) (a) + ((b).c)
c) (a + (b)).c
d) a + ((b).c)*
216. • Which of the following regular expressions represents the set of strings
which do not contain a substring ‘rt’ if ∑= {r, t}
a) (rt)*
b) (tr)*
c) (r t)**
d) (t* r*)
217. • According to the precedence rules, x - y - z is equivalent to which of the
following?
a) (x - y) - z
b) x - (y - z)
c) Both (x - y) - z and x - (y - z)
d) None of the mentioned
218. • Dot operator in regular expression resembles which of the following?
a) Expressions are juxtaposed
b) Expressions are multiplied
c) Cross operation
d) None of the mentioned
219. • Which among the following is not an associative operation?
a) Union
b) Concatenation
c) Dot
d) None of the mentioned
220. • Which among the following is equivalent to the given regular expression?
01* + 1
a) (01)* + 1
b) 0((1)* + 1)
c) (0(1)*) + 1
d) ((01)1)*
221. Which of the following is the same as the given DFA?
(0+1)001(0+1) is same as the given DFA in the string as an essential substring

a) (0+1)001(0+1)
b) 1001(0+1)
c) (01)(0+0+1)(01)
d) None of the mentioned

222. Which of the following statements is not true?

a) Every language defined by any of the automata is also defined by a regular
expression
b) Every language defined by a regular expression can be represented using a
DFA
c) Every language defined by a regular expression can be represented using NFA with
ε moves
d) Regular expression is just another representation for any automata definition
223. The total number of states required to automate the given regular expression
(00)(11)
a) 3
b) 4
c) 5
d) 6
224. Which of the given regular expressions correspond to the automata shown?
The regular expressions correspond to the automata is (110+11)*0

a) (110+1)*0
b) (11+110)*1
*c) (110+11)0
d) (1+110)*1

225. Generate a regular expression for the following problem statement:

P(x): String of length 6 or less for Σ = {0,1}*
a) (1+0+ε)^6
b) (10)^6
c) (1+0)(1+0)(1+0)(1+0)(1+0)(1+0)
d) More than one of the mentioned is correct
226. The minimum number of states required in a DFA (along with a dumping
state) to check whether the 3rd bit is 1 or not for |n| ≥ 3
a) 3
b) 4
c) 5
d) 1
227. Which of the regular expressions corresponds to the given problem statement:
P(x): Express the identifiers in C Programming language
l = letters
d = digits
a) (l+)(d+)*
b) (l+d+)*
**c) (l+)(l+d+)* **
d) (+d)(l+d+_)*
228. Generate a regular expression for the given language:
L(x): {x ∈ {0,1}* | x ends with 1 and does not contain a substring 01}
a) (0+01)*
b) (0+01)1
c) (0+01)(1+01)
d) All of the mentioned
229. The minimum number of transitions to pass to reach the final state as per the
following regular expression is:
{a,b}*{baaa}
a) 4
b) 5
c) 6
d) 3
230. Which of the following is an utility of state elimination phenomenon?
a) DFA to NFA
b) NFA to DFA
c) DFA to Regular Expression
d) All of the mentioned
231. If we have more than one accepting state or an accepting state with an
outdegree, which of the following actions will be taken?
a) addition of new state
b) removal of a state
c) make the newly added state as final
d) more than one option is correct
232. Which of the following is not a step in elimination of states procedure?
a) Unifying all the final states into one using ε-transitions
b) Unify single transitions to multi transitions that contain union of input
c) Remove states until there is only starting and accepting states
d) Get the resulting regular expression by direct calculation
233. Can the given state diagram be reduced?
The state q2 can be eliminated with ease

a) Yes
b) No

234. Which of the following methods is suitable for conversion of DFA to RE?
a) Brzozowski method
b) Arden’s method
c) Walter’s method
d) All of the mentioned
235. State true or false:
Statement: The state removal approach identifies patterns within the graph and
removes state, building up regular expressions along each transition.
a) true
b) false
236. The behavior of NFA can be simulated using DFA.
a) always
b) never
c) sometimes
d) none of the mentioned
237. It is suitable to use ____________ method/methods to convert a DFA to
regular expression.
a) Transitive Closure properties
b) Brzozowski method
c) State elimination method
d) All of the mentioned
238. State true or false:
Statement: For every removed state, there is a regular expression produced.
a) true
b) false
239. Is it possible to obtain more than one regular expression from a given DFA
using the state elimination method?
a) Yes
b) No
240. • A regular language over an alphabet a is one that can be obtained from
a) union
b) concatenation
c) Kleene
d) All of the mentioned
241. • Regular expression {0,1} is equivalent to
a) 0 U 1
b) 0 / 1
c) 0 + 1
d) All of the mentioned
242. • Precedence of regular expression in decreasing order is
a) * , . , + (correct)
b) . , * , +
c) . , + , *
d) + , a , *
243. • Regular expression Φ* is equivalent to
a) ε
b) Φ
c) 0
d) 1
244. • a? is equivalent to
a) a
b) a + Φ
c) a + ε (correct)
d) wrong expression
245. • εL is equivalent to
a) ε
b) Φ
c) L
d) Φε
246. • (a + b)* is equivalent to
a) b* a*
b) (a* b*)*
c) a* b*
d) none of the mentioned
247. • ΦL is equivalent to
a) LΦ & Φ
b) Φ & L
c) L & L
d) ε & L
248. • Which of the following pairs of regular expressions are not equivalent?
a) 1(01)* and (10)1
b) x(xx) and (xx)x
c) (ab) and ab**
d) x+ and x*x+
249. • Consider the following regular expressions:
i) (a/b)*
ii) (a*/b*)*
iii) ((ε/a)b*)*
Which of the following statements is correct?
a) i, ii are equal and ii, iii are not
b) i, ii are equal and i, iii are not
c) ii, iii are equal and i, ii are not
d) all are equal
250. • How many strings of length less than 4 contains the language described by
the regular expression (x + y)* y (a + ab)*?
a) 7
b) 10
c) 12
d) 11
251. • Which of the following is true?
a) (01)0 = 0(10)
b) (0 + 1)0(0 + 1)1(0 + 1) = (0 + 1)01(0 + 1)
c) (0 + 1)01(0 + 1) + 10 = (0 + 1)*
d) All of the mentioned
252. • A language is regular if and only if
a) accepted by DFA
b) accepted by PDA
c) accepted by LBA
d) accepted by Turing machine
253. • Regular grammar is
a) context free grammar
b) non context free grammar
c) english grammar
d) none of the mentioned
254. • Let the class of language accepted by finite state machine be L1 and the
class of languages represented by regular expressions be L2 then
a) L1 < L2
b) L1 >= L2
c) L1 U L2 = .*
d) L1 = L2
255. • Which of the following is not a regular expression?
a) [(a + b)* - (aa + bb)]*
b) [(0 + 1) - (0b + a1)(a + b)]
c) (01 + 11 + 10)*
d) (1 + 2 + 0)(1 + 2)
256. • Regular expressions are
a) Type 0 language
b) Type 1 language
c) Type 2 language
d) Type 3 language
257. • Which of the following is true?
a) Every subset of a regular set is regular
b) Every finite subset of non-regular set is regular
c) The union of two non-regular sets is not regular
d) Infinite union of finite set is regular
258. • L and ~L are recursively enumerable then L is
a) Regular
b) Context free
c) Context sensitive
d) Recursive
259. • Regular expressions are closed under
a) Union
b) Intersection
c) Kleene star
d) All of the mentioned

1. What kind of expressions do we use for pattern matching?

a) Regular Expression
b) Rational Expression
c) Regular & Rational Expression
d) None of the mentioned
2. Which of the following do Regexps not find their use in?
a) search engines
b) word processors
c) sed
d) none of the mentioned
 3. Which of the following languages have built-in regexps support?
a) Perl
b) Java
c) Python
d) C++
4. The following is/are an approach to process a regexp:
a) Construction of NFA and subsequently, a DFA
b) Thompson’s Construction Algorithm
c) Thompson’s Construction Algorithm & Construction of NFA and
subsequently, a DFA
d) None of the mentioned
5. Are the given two patterns equivalent?
(1) gray|grey
(2) gr(a|e)y
a) yes
b) no
6. Which of the following are not quantifiers?
a) Kleene plus +
b) Kleene star *
c) Question mark ?
d) None of the mentioned
7. Which of the following cannot be used to decide whether and how a given regexp
matches a string:
a) NFA to DFA
b) Lazy DFA algorithm
c) Backtracking
d) None of the mentioned
8. What does the following segment of code output?

perl
CopyEdit
$string1 = "Hello World\n";
if ($string1 =~ m/(H..).(l..)/) {
print "We matched '$1' and '$2'.\n";
}

a) We matched ‘Hel’ and ‘ld’

b) We matched ‘Hel’ and ‘lld’
c) We matched ‘Hel’ and ‘lo ’
d) None of the mentioned

9. Given segment of code:

perl
CopyEdit
$string1 = "Hello\nWorld\n";
if ($string1 =~ m/d\n\z/) {
print "$string1 is a string ";
print "that ends with 'd\\n'.\n";
}
What does the symbol /\z/ do?
a) changes line
b) matches the beginning of a string
c) matches the end of a string
d) none of the mentioned

10. Conversion of a regular expression into its corresponding NFA :

a) Thompson’s Construction Algorithm
b) Powerset Construction
c) Kleene’s algorithm
d) None of the mentioned

260. Ff

261. Which among the following is not a UNIX command for regular expressions?
a) ed
b) sed
c) vi
d) none of the mentioned
262. What is the significance of $ used in regular expression in UNIX?
a) Matches the beginning of the line
b) Matches the end of lines
c) Matches any single character
d) None of the mentioned
263. Generate the regular expression to match blank lines
a) / */
b) /bl
c) /^?/
d) /^$/
264. For the given syntax of sed, which among the following is not a correct
option?
General syntax of sed: /pattern/action
a) / are used as delimiters
b) pattern refers to a regular expression
c) pattern refers to the string to be matched
d) action refers to the command
265. What does grep do in UNIX?
a) It is an editor in UNIX
b) It searches for text patterns
c) It is an editor in UNIX and it searches for text patterns
d) None of the mentioned
266. State true or false:
Statement: A regular expression is a sequence of characters that represent a pattern.
a) true
b) false
267. Which of the following options support the given statement?
Statement: A regular expression could be a fixed word or describe something more
general.
a) This flexibility makes Regular expression invaluable
b) This flexibility makes the Regular expression unvaluable
c) This flexibility makes Regular expression invaluable and unvaluable
d) None of the mentioned
268. What does the following segment of code do?
grep -i man heroes.txt
a) manually opens a file called heroes.txt
b) manages heroes.txt
c) search for “man” in the file “heroes.txt”
d) none of the mentioned
269. What does “X?” do in regular expression operator?
a) Matches zero or more capital X’s
b) Matches no or one occurrence of the capital letter X
c) Matches one or more capital X’s
d) All of the mentioned
270. Which of the following does not support regular expressions?
a) sed
b) awk
c) emacs
d) none of the mentioned
271. • Lexemes can be referred to as:
a) elements of lexicography
b) sequence of alphanumeric characters in a token
c) lexical errors
d) none of the mentioned
272. • If the lexical analyser finds a lexeme with the same name as that of a
reserved word, it _________
a) overwrites the word
b) overwrites the functionality
c) generates an error
d) something else
273. • The methodology to show an error when the analyzer faces a keyword over
a user’s input is based on:
a) rule priority
b) longest match rule
c) keyword-out rule
d) none of the mentioned
274. • State true or false:
Statement: A lexical analyzer reads the source code line by line.
a) True
b) False
275. • Which among the following statement is correct?
Statement 1: When the analyzer scans ‘int’ and ‘intvalue’, it is not able to decide
whether the int leads to a keyword or an identifier.
Statement 2: Longest Match Rule
a) Statement 1 is assertion, Statement 2 is the reason
b) Statement 1 is assertion, Statement 2 is the solution
c) There is no such Statement 2
d) This is not a function of Lexical Analyzer
276. • The output of the lexical and syntax analyzer can be stated as:
a) parse stream, parse tree
b) token tree, parse tree
c) token stream, parse tree
d) all of the mentioned
277. • Which among the following is not a tool to construct lexical analyzer from a
regular expression?
a) lex
b) flex
c) jflex
d) none of the mentioned
278. • A program that performs lexical analysis is termed as:
a) scanner
b) lexer
c) tokenizer
d) all of the mentioned
279. • Lexers and parsers are not found in which of the following?
a) compiler front end processing
b) prettyprinters
c) linters
d) none of the mentioned
280. • Which phase of compiler includes Lexical Analysis?
a) 1
b) 2
c) 3
d) Its primary function, not in any phase
281. • Which of the following characters are ignored while lexical analysis?
a) .
b) =
c) #
d) WhiteSpace
282. • ____________ is used for grouping up of characters into token.
a) Lexical Analyzer
b) oolex
c) jflex
d) All of the mentioned
283. • The action of parsing the source code into proper syntactic classes is known
as:
a) Parsing
b) Interpretation analysis
c) Lexicography
d) Lexical Analysis
284. • Which of the following is the task of lexical analysis?
a) To build the uniform symbol table
b) To initialize the variables
c) To organize the variables in a lexical order
d) None of the mentioned
285. • The scanner outputs:
a) Stream of tokens
b) Image file
c) Intermediate code
d) Machine code
286. • The phase of compilation which involves type checking is:
a) Parsing
b) Scanning
c) Syntax directed translation
d) Semantic Analyzer
287. • The minimum length of a string {0,1}* not in the language corresponding to
the given regular expression:
(0* + 1*) (0* + 1*) (0* + 1*)
a) 3
b) 4
c) 5
d) 6
288. • Which of the following regular expressions is equivalent to R(1,0)?
R(1,0) = {111*}*
a) (11 + 111)*
b) (111 + 1111)*
c) (111 + 11*)*
d) All of the mentioned
289. • The minimum number of 1’s to be used in a regular expression of the given
language:
R(x): The language of all strings containing exactly 2 zeroes.
a) 2
b) 3
c) 0
d) 1
290. • The given regular language corresponds to which of the given regular
languages:
ε + 1 + (1 + 0)* 0 + (0 + 1)* 11
a) The language of all strings that end with 11 or 00
b) The language of all strings that end with 0 or 1
c) The language of all strings which does not end with 01
d) None of the mentioned
291. • Statement: If we take the union of two identical expressions, we can replace
them by one copy of the expression.
Which of the following is a correct option for the given statement?
a) Absorption Law
b) Idempotent Law
c) Closure Law
d) Commutative Law
292. • Which among the following can be an annihilator for multiplication
operation?
a) 0
b) 1
c) 100
d) 22/7
293. • Statement: A digit, when used in the CFG notation, will always be used as a
terminal.
State true or false?
a) True
b) False
294. • Choose the incorrect process to check whether the string belongs to the
language of certain variable or not?
a) recursive inference
b) derivations
c) head to body method
d) All of the mentioned
295. • Statement: Left most derivations are lengthy as compared to Right most
derivations.
Choose the correct option:
a) correct statement
b) incorrect statement
c) may or may not be correct
d) depends on the language of the grammar
296. • A -> aAa | bAb | a | b | ε
Which among the following is the correct option for the given production?
a) Left most derivation
b) Right most derivation
c) Recursive Inference
d) None of the mentioned
297. • All the regular languages can have one or more of the following
descriptions:
i) DFA
ii) NFA
iii) ε-NFA
iv) Regular Expressions
Which of the following are correct?
a) i, ii, iv
b) i, ii, iii
c) i, iv
d) i, ii, iii, iv
298. • Which of the techniques can be used to prove that a language is non
regular?
a) Arden’s theorem
b) Pumping Lemma
c) Ogden’s Lemma
d) None of the mentioned
299. • Which of the following languages is regular?
a) {a^i b^i | i ≥ 0}
b) {a^i b^i | 0 < i < 5}
c) {a^i b^i | i ≥ 1}
d) None of the mentioned
300. • Which of the following are non-regular?
a) The set of strings in {a,b}* with an even number of b’s
b) The set of strings in {a,b,c}* where there is no c anywhere to the left of a
c) The set of strings in {0,1}* that encode, in binary, an integer w that is a multiple of
3. Interpret the empty string ε as the number 0
d) None of the mentioned
301. • If L is DFA-regular, L’ is
a) Non regular
b) DFA-regular
c) Non-finite
d) None of the mentioned
302. • Which of the following options is incorrect?
a) A language L is regular if and only if ~L has finite number of equivalent classes
b) Let L be a regular language. If ~L has k equivalent classes, then any DFA that
recognizes L must have at most k states
c) A language L is NFA-regular if and only if it is DFA-regular
d) None of the mentioned
303. • Myhill-Nerode does the following:
a) Minimization of DFA
b) Tells us exactly when a language is regular
c) Minimization of DFA and tells us exactly when a language is regular
d) None of the mentioned
304. • Which of the following are related to tree automaton?
a) Myhill-Nerode Theorem
b) State machine
c) Courcelle’s Theorem
d) All of the mentioned
305. • Given languages:
i) {a^n b^n | n ≥ 0}
ii) <div>n</div>n (assuming HTML tags; likely non-regular)
iii) {w ∈ {a,b}* | #a(w) = #b(w)}, # represents occurrences
Which of the following is/are non regular?
a) i, iii
b) i
c) iii
d) i, ii, iii
306. • Finite state machines are not able to recognize Palindromes because:
a) Finite automata cannot deterministically find the midpoint
b) Finite automata cannot remember arbitrarily large amount of data
c) Even if the midpoint is known, it cannot find whether the second half matches the
first
d) All of the mentioned
307. • Relate the following statement:
Statement: All sufficiently long words in a regular language can have a middle section
of words repeated a number of times to produce a new word which also lies within the
same language.
a) Turing Machine
b) Pumping Lemma
c) Arden’s theorem
d) None of the mentioned
308. • While applying Pumping lemma over a language, we consider a string w
that belongs to L and fragment it into _________ parts.
a) 2
b) 5
c) 3
d) 6
309. • If we select a string w such that w ∈ L, and w = xyz. Which of the following
portions cannot be an empty string?
a) x
b) y
c) z
d) all of the mentioned
310. • Let w = xyz and y refers to the middle portion and |y| > 0. What do we call
the process of repeating y 0 or more times before checking that they still belong to the
language L or not?
a) Generating
b) Pumping
c) Producing
d) None of the mentioned
311. • There exists a language L. We define a string w such that w ∈ L and w =
xyz and |w| ≥ n for some constant integer n. What can be the maximum length of the
substring xy i.e. |xy| ≤ ?
a) n
b) |y|
c) |x|
d) none of the mentioned
312. • Fill in the blank in terms of p, where p is the maximum string length in L.
Statement: Finite languages trivially satisfy the pumping lemma by having n =
______
a) p*1
b) p + 1
c) p - 1
d) None of the mentioned
313. • Answer in accordance to the third and last statement in pumping lemma:
For all _______ xy^i z ∈ L
a) i > 0
b) i < 0
c) i ≤ 0
d) i ≥ 0
314. • If d is a final state, which of the following is correct according to the given
diagram?
x = p, y = qr, z = s is correct order according to the diagram if d is a final state

a) x = p, y = qr, z = s
b) x = p, z = qrs
c) x = pr, y = r, z = s
d) All of the mentioned

315. • Let w be a string and fragmented by three variables x, y, and z as per

pumping lemma. What do these variables represent?
a) string count
b) string
c) string count and string
d) none of the mentioned
316. • Which of the following one can relate to the given statement:
Statement: If n items are put into m containers, with n > m, then at least one container
must contain more than one item.
a) Pumping lemma
b) Pigeon Hole principle
c) Count principle
d) None of the mentioned
317. • Which kind of proof is used to prove the regularity of a language?
a) Proof by contradiction
b) Direct proof
c) Proof by induction
d) None of the mentioned
318. • The language of balanced parentheses is
a) regular
b) non regular
c) may be regular
d) none of the mentioned
319. • State true or false:
Statement: Pumping lemma gives a necessary but not sufficient condition for a
language to be regular.
a) true
b) false
320. • Which of the following is/are an example of pigeonhole principle?
a) Softball team
b) Sock picking
c) Hair counting
d) All of the mentioned
321. • Pigeonhole principle can be applied in the following computer science
algorithms:
a) hashing algorithm
b) lossless compression algorithm
c) hashing algorithm and lossless compression algorithm
d) none of the mentioned
322. • If n objects are distributed over m places, and n < m, then some of the
places receive:
a) at least 2 objects
b) at most 2 objects
c) no object
d) none of the mentioned
323. • Which of the following fields may have pigeonhole principle violated?
a) Discrete mathematics
b) Computer Science
c) Quantum Mechanics
d) None of the mentioned
324. • Which of the following is not an application of Pumping Lemma?
a) {0^i 1^i | i >= 0}
b) {0^i x | i >= 0, x ∈ {0,1}* and |x| ≤ i}
c) {0^n | n is prime}
d) None of the mentioned
325. • Which of the following can refer a language to be non regular?
a) Pumping Lemma
b) Myhill Nerode
c) Pumping Lemma and Myhill Nerode
d) None of the mentioned
326. • Which of the following is not an example of counting argument?
a) Pigeonhole principle
b) Dirichlet’s drawer principle
c) Dirichlet’s box principle
d) None of the mentioned
327. If L1, L2 are regular and op(L1, L2) is also regular, then L1 and L2 are said to
be ____________ under an operation op.
a) open
b) closed
c) decidable
d) none of the mentioned
328. Suppose a regular language L is closed under the operation halving, then the
result would be:
a) 1/4 L will be regular
b) 1/2 L will be regular
c) 1/8 L will be regular
d) All of the mentioned
329. If L1′ and L2′ are regular languages, then L1.L2 will be
a) regular
b) non regular
c) may be regular
d) none of the mentioned
330. If L1 and L2′ are regular languages, L1 ∩ (L2′ U L1′)’ will be
a) regular
b) non regular
c) may be regular
d) none of the mentioned
331. If A and B are regular languages, !(A’ U B’) is:
a) regular
b) non regular
c) may be regular
d) none of the mentioned
332. Which among the following are the boolean operations that under which
regular languages are closed?
a) Union
b) Intersection
c) Complement
d) All of the mentioned
333. Suppose a language L1 has 2 states and L2 has 2 states. After using the cross
product construction method, we have a machine M that accepts L1 ∩ L2. The total
number of states in M:
a) 6
b) 4
c) 2
d) 8
334. If L is a regular language, then (L’)’ U L will be :
a) L
b) L’
c) f
d) none of the mentioned
335. If L is a regular language, then (((L’)r)’)* is:
a) regular
b) non regular
c) may be regular
d) none of the mentioned
336. Which among the following is the closure property of a regular language?
a) Emptiness
b) Universality
c) Membership
d) None of the mentioned
337. • If L is a language, the reversal of the language can be represented as:
a) L’
b) Lc
c) Lr
d) more than one option is correct
338. • If L is a regular language, ____ is also regular.
a) Lr
b) L’
c) L*
d) All of the mentioned
339. • If E = F + G;
Er = ?
a) Fr + Gr
b) (F + G)r
c) Fr + Gr and (F + G)r
d) None of the mentioned
340. • If E = FG, Er = ?
a) FrGr
b) GrFr
c) FrGr and GrFr
d) None of the mentioned
341. • Simplify the following identity:
E = 01* + 10*
ER = ?
a) (10 + 01)
b) (0110)R
c) (01 + 10)
d) All of the mentioned
342. • Which of the following obey the closure properties of Regular language?
a) Homomorphism
b) Inverse Homomorphism
c) Reversal
d) All of the mentioned
343. • Let h(L) be a language of regular expression abe* + e(ab). Simplify the h(L)
a) (ab) + eab*
b) abe* + eab
c) (ab)*
d) None of the mentioned
344. • Let h(0) = ab; h(1) = e
Let L = {abab, baba}
h⁻¹(L) = _______
a) the language of two one’s and any number of zeroes
b) the language of two zeroes and any number of one’s
c) the language of two zeroes and two one’s
d) none of the mentioned
345. • While proving Inverse Homomorphism, which of the following steps are
needed?
a) Start with a DFA A in L
b) Construct a DFA B for h⁻¹(L)
c) The set of states, initial and final states should be same
d) All of the mentioned
346. • Let h(0) = ab; h(1) = e
Let L = {abab, baba}
h⁻¹(L) = the language of two zeroes and any number of one’s.
The given example belongs to which of the following?
a) Homomorphism
b) Inverse Homomorphism
c) Homomorphism and Inverse Homomorphism
d) None of the mentioned
347. • Which of the following conversion is not feasible?
a) Regular expression to automaton conversion
b) Automaton to Regular Expression Conversion
c) NFA to DFA
d) None of the mentioned
348. • The computation of ε-closure of n-states takes ______ time.
a) O(n²)
b) O(n³)
c) O(2ⁿ)
d) None of the mentioned
349. • For a _________ state DFA, the time taken for DFA-NFA conversion is
O(n).
a) n
b) n¹ᐟ²
c) n²
d) 2ⁿ
350. • With reference to Automaton to Regular Expression Conversion, for each of
the n rounds, where n is the number of states of DFA, we can _________ the size of
the regular expression constructed.
a) double
b) triple
c) quadruple
d) none of the mentioned
351. • Conversion of regular expression to ε-NFA takes ___________ time.
a) linear
b) exponential
c) logarithmic
d) none of the mentioned
352. • The conversion of NFA to DFA can be done in:
a) exponential time
b) linear time
c) logarithmic time
d) all of the mentioned
353. • Which of the following cannot be converted in an ordinary NFA?
a) DFA
b) Regular Expression
c) ε-NFA
d) None of the mentioned
354. • NFA to DFA conversion is done via
a) Subset Construction method
b) Warshall’s Algorithm
c) Arden’s theorem
d) None of the mentioned
355. • State true or false:
Statement: Regular expression can directly be converted to DFA without intermediate
steps.
a) true
b) false
356. • Is the following statement correct?
Statement: Thompson construction is used to convert Regular expression to finite
automata.
a) Yes
b) No
357. • Language classes have the following property:
a) Closure property
b) Decision property
c) Closure & Decision property
d) None of the mentioned
358. • Which of the following are decision properties?
a) Emptiness
b) Infiniteness
c) Membership
d) All of the mentioned
359. • Pick the odd one out of the given properties of a regular language:
a) Kleene
b) Reversal
c) Homomorphism
d) Membership
360. • For an automaton, which of the following are equivalent variants?
DFA, NFA and NFA with epsilon transitions
a) DFA and NFA
b) NFA and epsilon NFA
c) DFA and epsilon NFA
d) All of the mentioned
361. • Which of the following are not meant to specify a regular language?
a) Regular Expression
b) DFA
c) NDFA and epsilon-NFA
d) All of the mentioned
362. • Which of the following problems do not belong to decision properties?
a) Given two languages, are there strings that are in both
b) Is the language a subset of another regular language
c) Is the language same as another regular language
d) None of the mentioned
363. • Which of the following is a function of Closure properties?
a) Helps construct representations
b) Helps show informally described languages not to be in class
c) Helps construct representations and shows informally described languages not
to be in class
d) None of the mentioned
364. • Suppose there is a string w = abbab, and there exists a DFA which accepts
w. How many steps will be required to test its membership?
a) 2
b) 1
c) 4
d) 5
365. • If a DFA has n states and the language contains any string of length n or
more, the language is termed as:
a) Infinite
b) Empty
c) Non regular
d) None of the mentioned
366. • State true or false:
Statement: If an n-state DFA accepts a string w of length n or more, then there must
be a state that appears twice on the path labeled w from the start state to the final
state.
a) true
b) false
367. • The entity which generate Language is termed as:
a) Automata
b) Tokens
c) Grammar
d) Data
368. • Production Rule: aAb -> agb belongs to which of the following category?
a) Regular Language
b) Context free Language
c) Context Sensitive Language
d) Recursively Enumerable Language
369. • Which of the following statement is false?
a) Context free language is the subset of context sensitive language
b) Regular language is the subset of context sensitive language
c) Recursively enumerable language is the super set of regular language
d) Context sensitive language is a subset of context free language
370. • The Grammar can be defined as: G = (V, ∑, p, S)
In the given definition, what does S represent?
a) Accepting State
b) Starting Variable
c) Sensitive Grammar
d) None of these
371. • Which among the following cannot be accepted by a regular grammar?
a) L is a set of numbers divisible by 2
b) L is a set of binary complement
c) L is a set of string with odd number of 0
d) L is a set of 0ⁿ1ⁿ
372. • Which of the expression is appropriate?
For production p: a -> b where a ∈ V and b ∈ _______
a) V
b) S
*c) (V + ∑) **
d) V + ∑
373. • For S -> 0S1 | ε for ∑ = {0,1}*, which of the following is wrong for the
language produced?
a) Non regular language
b) 0ⁿ1ⁿ | n ≥ 0
c) 0ⁿ1ⁿ | n ≥ 1
d) None of the mentioned
374. • The minimum number of productions required to produce a language
consisting of palindrome strings over ∑ = {a, b} is
a) 3
b) 7
c) 5
d) 6
375. • Which of the following statement is correct?
a) All Regular grammar are context free but not vice versa
b) All context free grammar are regular grammar but not vice versa
c) Regular grammar and context free grammar are the same entity
d) None of the mentioned
376. • Are ambiguous grammar context free?
a) Yes
b) No
377. • Which of the following is not a notion of Context free grammars?
a) Recursive Inference
b) Derivations
c) Sentential forms
d) All of the mentioned
378. • State true or false:
Statement: The recursive inference procedure determines that string w is in the
language of the variable A, A being the starting variable.
a) true
b) false
379. • Which of the following is/are the suitable approaches for inferencing?
a) Recursive Inference
b) Derivations
c) Recursive Inference and Derivations
d) None of the mentioned
380. • If w belongs to L(G), for some CFG, then w has a parse tree, which defines
the syntactic structure of w. w could be:
a) program
b) SQL-query
c) XML document
d) All of the mentioned
381. • Is the following statement correct?
Statement: Recursive inference and derivation are equivalent.
a) Yes
b) No
382. • A -> aA | a | b
The number of steps to form aab:
a) 2
b) 3
c) 4
d) 5
383. • An expression is mentioned as follows. Figure out number of incorrect
notations or symbols, such that a change in those could make the expression correct.
L(G) = { w in T* | S →* w }
a) 0 Errors
b) 1 Error
c) 2 Error
d) Invalid Expression
384. • The language accepted by Push down Automaton:
a) Recursive Language
b) Context free language
c) Linearly Bounded language
d) All of the mentioned
385. • Which among the following is the correct option for the given grammar?
G -> X111 | G1, X -> X0 | 00
a) {0^a1^b | a=2, b=3}
b) {0^a1^b | a=1, b=5}
c) {0^a1^b | a=b}
d) More than one of the mentioned is correct
386. • Which of the following the given language belongs to?
L = { a^m b^m c^m | m ≥ 1 }
a) Context free language
b) Regular language
c) Context free language & Regular language
d) None of the mentioned
387. • Choose the correct option:
Statement: There exists two inference approaches: Recursive Inference & Derivation
a) true
b) partially true
c) false
d) none of the mentioned
388. • Choose the correct option:
Statement 1: Recursive Inference, using productions from head to body.
Statement 2: Derivations, using productions from body to head.
a) Statement 1 is true and Statement 2 is true
b) Statement 1 and Statement 2, both are false
c) Statement 1 is true and Statement 2 is false
d) Statement 2 is true and Statement 1 is true
389. • Which of the following statements are correct for a concept called inherent
ambiguity in CFL?
a) Every CFG for L is ambiguous
b) Every CFG for L is unambiguous
c) Every CFG is also regular
d) None of the mentioned
390. • Which of the theorem defines the existence of Parikh’s theorem?
a) Parikh’s theorem
b) Jacobi theorem
c) AF+BG theorem
d) None of the mentioned
391. • State true or false:
Statement: Every right-linear grammar generates a regular language.
a) True
b) False
392. • What does the given CFG define?
S -> aSbS | bSaS | ε and w denotes terminal
a) wwr
b) wSw
c) Equal number of a’s and b’s
d) None of the mentioned
393. • If L1 and L2 are context free languages, which of the following is context
free?
a) L1*
b) L2 U L1
c) L1.L2
d) All of the mentioned
394. • For the given Regular expression, the minimum number of variables
including starting variable required to derive its grammar is:
(011 + 1)* (01)*
a) 4
b) 3
c) 5
d) 6
395. • For the given Regular expression, the minimum number of terminals
required to derive its grammar is:
(011 + 1)* (01)*
a) 4
b) 3
c) 5
d) 6
396. • A grammar G = (V, T, P, S) is __________ if every production takes one of
the two forms:
B -> aC
B -> a
a) Ambiguous
b) Regular
c) Non Regular
d) None of the mentioned
397. • Which among the following is a CFG for the given Language:
L = { x ∈ {0,1}* | number of zeroes in x = number of one’s in x }
a) S -> ε | 0S1 | 1S0 | SS
b) S -> 0B | 1A | ε ; A -> 0S ; B -> 1S
c) All of the mentioned
d) None of the mentioned
398. • Which of the following languages are most suitable for implementing
context free languages?
a) C
b) Perl
c) Assembly Language
d) None of the mentioned
399. • Which among the following is the correct grammar for the given language?
L = { x ∈ {0,1}* | number of zeroes in x ≠ number of one’s in x }
a) S -> 0 | SS | 1SS | SS1 | S1S
b) S -> 1 | 0S | 0SS | SS0 | S0S
c) S -> 0 | 0S | 1SS | SS1 | S1S
d) None of the mentioned
400. • L = {0ⁱ1ʲ2ᵏ | j > i + k}
Which of the following satisfies the language?
a) 0111100
b) 011100
c) 0001100
d) 0101010
401. • The most suitable data structure used to represent the derivations in
compiler:
a) Queue
b) Linked List
c) Tree
d) Hash Tables
402. • Which of the following statement is false in context of tree terminology?
a) Root with no children is called a leaf
b) A node can have three children
c) Root has no parent
d) Trees are collection of nodes, with a parent child relationship
403. • In which order are the children of any node ordered?
a) From the left
b) From the right
c) Arbitrarily
d) None of the mentioned
404. • Which among the following is the root of the parse tree?
a) Production P
b) Terminal T
c) Variable V
d) Starting Variable S
405. • For the expression E * (E) where * and brackets are the operation, number
of nodes in the respective parse tree are:
a) 6
b) 7
c) 5
d) 2
406. • The number of leaves in a parse tree with expression E * (E) where * and ()
are operators:
a) 5
b) 2
c) 4
d) 3
407. • Which of the following does the given parse tree correspond to?
The following is a parse tree for the production 0110 over {0,1}*

a) P -> 1100
b) P -> 0110
c) P -> 1100ε
d) P -> 0101

408. • A grammar with more than one parse tree is called:

a) Unambiguous
b) Ambiguous
c) Regular
d) None of the mentioned
409. • __________ is the acyclic graphical representation of a grammar.
a) Binary tree
b) Oct tree
c) Parse tree
d) None of the mentioned
410. • Grammar is checked by which component of compiler?
a) Scanner
b) Parser
c) Semantic Analyzer
d) None of the mentioned
411. • A symbol X is ________ if there exists : S->* aXb
a) reachable
b) generating
c) context free
d) none of the mentioned
412. • A symbol X is called to be useful if and only if it is:
a) generating
b) reachable
c) both generating and reachable
d) none of the mentioned
413. • Which of the following is false for a grammar G in Chomsky Normal Form:
a) G has no useless symbols
b) G has no unit productions
c) G has no epsilon productions
d) None of the mentioned
414. • Given Checklist:
i) G has no useless symbols
ii) G has no unit productions
iii) G has no epsilon productions
iv) Normal form for production is violated
Is it possible for the grammar G to be in CNF with the following checklist?
a) Yes
b) No
415. • State true or false:
Statement: A CNF parse tree’s string yield (w) can no longer be 2h-1.
a) true
b) false
416. • If |w|>=2h, then its parse tree’s height is at least _____
a) h
b) h+1
c) h-1
d) 2h
417. • If w belongs to L(G), for some CFG, then w has a parse tree, which tell us
the ________ structure of w.
a) semantic
b) syntactic
c) lexical
d) all of the mentioned
418. • Which of the following are distinct to parse trees?
a) abstract parse trees
b) sentence diagrams
c) both abstract parse trees and sentence diagrams
d) none of the mentioned
419. • Choose the correct option:
Statement: Unambiguity is the ideal structure of a language.
a) true
b) partially true
c) false
d) cant be said
420. • Is the given statement correct?
Statement: The mere existence of several derivations is not an issue, it is the existence
of several parse trees that ruins a grammar.
a) Yes
b) No
421. • To derive a string using the production rules of a given grammar, we use:
a) Scanning
b) Parsing
c) Derivation
d) All of the mentioned
422. • Which of the following parser reaches the root symbol of the tree at last?
a) Top down parser
b) Bottom up parser
c) TOP down and Bottom up parser
d) None of the mentioned
423. • Left corner parsing method uses which of the following?
a) Top down parser
b) Bottom up parser
c) TOP down and Bottom up parser
d) None of the mentioned
424. • Which of the following parser performs top down parsing?
a) LALR parser
b) LL parser
c) Recursive Accent parser
d) None of the mentioned
425. • Which of the following is true for shift reduce parsers?
a) Scans and parses the input in one forward pass over the text, without any backup
b) A shift command advances in the input stream by one symbol
d) All of the mentioned
c) LALR parser
426. • State true or false:
Statement: LALR parsers uses tables rather than mutually recursive functions.
a) true
b) false
427. • LALR in LALR parser stands for:
a) Left aligned left right parser
b) Look ahead left to right parser
c) Language Argument left to right parser
d) None of the mentioned
428. • Which of the following can be a LALR parser generator?
a) YACC
b) GNU Bison
c) YACC and GNU Bison
d) None of the mentioned
429. • Which of the following parsers do not relate to Bottom up parsing?
d) All of the mentioned
a) LL parser
b) Recursive descent parser
c) Earley parsers
430. • Which of the following is true for a predictive parser?
a) Recursive Descent parser
b) no backtracking
c) Recursive Descent parser and no backtracking
d) None of the mentioned
431. • YACC is a computer program for ______ operation system.
a) Windows
b) DOS
c) Unix
d) openSUSE
432. • YACC is an acronym for:
a) Yes Another Compile Compiler
b) Yet Another Compile Compiler
c) Yet Another Compiler Compiler
d) Yes Another Compiler Compiler
433. • The YACC takes C code as input and outputs_________
a) Top down parsers
b) Bottom up parsers
c) Machine code
d) None of the mentioned
434. • The _______ table is created by YACC.
a) LALR parsing
b) LL parsing
c) GLR parsing
d) None of the mentioned
435. • The original YACC as written in __________ language
a) R programming language
b) C programming language
c) B programming language
d) None of the mentioned
436. • Which of the following is false for B programming language?
a) Typeless
b) Influenced by PL/I
c) Designed by Dennis Ritchie
d) None of the mentioned
437. • Which of the following is false for BNF?
a) BNF means Backus Naur Form
b) It is a normal form used in Data base normalization
c) It is a notation technique for context free grammar
d) None of the mentioned
438. • State true or false:
Statement: BNF is a metasyntax used to express CFG
a) True
b) False
439. • Which of the following are not used to express CFG?
a) BNF
b) EBNF, ABNF
c) Van Wijngaarden form
d) None of the mentioned
440. • Which of the following version of Unix came up with YACC first?
a) V3
b) V5
c) CB UNIX
d) Unix-RT
441. • XML is a _________ markup language.
a) meta
b) beta
c) octa
d) peta
442. • XML uses _________ principle to formally describe the data.
a) DDL
b) DTD
c) DML
d) None of the mentioned
443. • Which among the following are true for an Extensible markup language?
a) Human Readable/ Machine Readable
b) Extended from SGML
c) Developed by www consortium
d) All of the mentioned
444. • Which of them have XML as their default format?
a) IWork
b) LibreOffice
c) OpenOffice
d) All of the mentioned
445. • A DTD is associated with a XML file by means of ___________
a) Function
b) <!DOCTYPE>
c) Macros
d) None of the mentioned
446. • Which of the following is not an example of electronic mark up?
a) HTML
b) LaTeX
c) PostScript
d) None of the mentioned
447. • troff and nroff are _________ in Unix.
a) functions
b) typesetting tools
c) System sofwares
d) none of the mentioned
448. • SGML stands for:
a) Standard Generalized Markup Language
b) Standardized General Markup Language
c) Standard General Markup Language
d) Standard Generalized Markdown Language
449. • Markup Languages are not used for which of the following?
a) playlists
b) content syndication
c) user interfaces
d) none of the mentioned
450. • Which of the following is incorrect for HTML5 markup construct?
a) Start tags: <section>
b) End tags: </section>
c) <img src= “abc.jpeg” >ABC</img>
d) None of the mentioned
451. • A CFG is ambiguous if
a) It has more than one rightmost derivations
b) It has more than one leftmost derivations
c) No parse tree can be generated for the CFG
d) None of the mentioned
452. • Which of the following are always unambiguous?
a) Deterministic Context free grammars
b) Non-Deterministic Regular grammars
c) Context sensitive grammar
d) None of the mentioned
453. • A CFG is not closed under
a) Dot operation
b) Union Operation
c) Concatenation
d) Iteration
454. • Which of the following is an real-world programming language ambiguity?
a) dangling else problem
b) halting problem
c) maze problem
d) none of the mentioned
455. • Which of the following is a parser for an ambiguous grammar?
a) GLR parser
b) Chart parser
c) All of the mentioned
d) None of the mentioned
456. • A language that admits only ambiguous grammar:
a) Inherent Ambiguous language
b) Inherent Unambiguous language
c) Context free language
d) Context Sensitive language
457. • Which of the following is an example of inherent ambiguous language?
a) {an|n>1}
b) {anbncmdm| n,m > 0}
c) {0n1n|n>0}
d) None of the mentioned
458. • State true or false:
Statement: R->R|T T->ε is an ambiguous grammar
a) true
b) false
459. • In context to ambiguity, the number of times the following programming
statement can be interpreted as:
Statement: if R then if T then P else V
a) 2
b) 3
c) 4
d) 1
460. • CFGs can be parsed in polynomial time using__________
a) LR parser
b) CYK algorithm
c) SLR parser
d) None of the mentioned
461. • A push down automaton employs ________ data structure.
a) Queue
b) Linked List
c) Hash Table
d) Stack
462. • State true or false:
Statement: The operations of PDA never work on elements, other than the top.
a) true
b) false
463. • Which of the following allows stacked values to be sub-stacks rather than
just finite symbols?
a) Push Down Automaton
b) Turing Machine
c) Nested Stack Automaton
d) None of the mentioned
464. • A non deterministic two way, nested stack automaton has n-tuple definition.
State the value of n.
a) 5
b) 8
c) 4
d) 10
465. • Push down automata accepts _________ languages.
a) Type 3
b) Type 2
c) Type 1
d) Type 0
466. • The class of languages not accepted by non deterministic, nonerasing stack
automata is _______
a) NSPACE(n2)
b) NL
c) CSL
d) All of the mentioned
467. • A push down automaton with only symbol allowed on the stack along with
fixed symbol.
a) Embedded PDA
b) Nested Stack automata
c) DPDA
d) Counter Automaton
468. • Which of the operations are eligible in PDA?
a) Push
b) Delete
c) Insert
d) Add
469. • A string is accepted by a PDA when
a) Stack is not empty
b) Acceptance state
c) All of the mentioned
d) None of the mentioned
470. • The following move of a PDA is on the basis of:
a) Present state
b) Input Symbol
c) Present state and Input Symbol
d) None of the mentioned
471. • If two sets, R and T has no elements in common i.e. RÇT=Æ, then the sets
are called
a) Complement
b) Union
c) Disjoint
d) Connected
472. • Which among the following is not a part of the Context free grammar tuple?
a) End symbol
b) Start symbol
c) Variable
d) Production
473. • A context free grammar is a ___________
a) A rule system for parsing formal languages
b) Regular grammar
c) Context sensitive grammar
d) None of the mentioned
474. • The closure property of context free grammar includes :
a) Kleene
b) Concatenation
c) Union
d) All of the mentioned
475. • Which of the following automata takes stack as auxiliary storage?
a) Finite automata
b) Push down automata
c) Turing machine
d) All of the mentioned
476. • Which of the following automata takes queue as an auxiliary storage?
a) Finite automata
b) Push down automata
c) Turing machine
d) All of the mentioned
477. • A context free grammar can be recognized by
a) Push down automata
b) 2 way linearly bounded automata
c) Push down automata & 2 way linearly bounded automata
d) None of the mentioned
478. • A null production can be referred to as:
a) String
b) Symbol
c) Word
d) All of the mentioned
479. • The context free grammar which generates a Regular Language is termed
as:
a) Context Regular Grammar
b) Regular Grammar
c) Context Sensitive Grammar
d) None of the mentioned
480. • NPDA stands for
a) Non-Deterministic Push Down Automata
b) Null-Push Down Automata
c) Nested Push Down Automata
d) All of the mentioned
481. • The production of the form A->B , where A and B are non terminals is
called
a) Null production
b) Unit production
c) Greibach Normal Form
d) Chomsky Normal Form
482. • Halting states are of two types. They are:
a) Accept and Reject
b) Reject and Allow
c) Start and Reject
d) None of the mentioned
483. • A push down automata can be represented as:
PDA= ε-NFA +[stack] State true or false:
a) true
b) false
484. • A pushdown automata can be defined as: (Q, ∑, G, q0, z0, A, d)
What does the symbol z0 represents?
a) an element of G
b) initial stack symbol
c) top stack alphabet
d) all of the mentioned
485. • Which of the following correctly recognize the symbol ‘|-‘ in context to
PDA?
a) Moves
b) transition function
c) or/not symbol
d) none of the mentioned
486. • Which among the following is true for the given statement?
Statement :If there are strings R and T in a language L so that R is prefix of T and R is
not equivalent to T.
a) No DPDA can accept L by empty stack
b) DPDA can accept L by an empty stack
c) L is regular
d) None of the mentioned
487. • Which of the following can be accepted by a DPDA?
a) The set of even length palindrome over {a,b}
b) The set of odd length palindrome over {a,b}
c) {xxc| where c stands for the complement,{0,1}}
d) None of the mentioned
488. • For a counter automaton, with the symbols A and Z0, the string on the stack
is always in the form of __________
a) A
b) AnZ0, n>=0
c) Z0An, n>=0
d) None of the mentioned
489. • State true or false:
Statement: Counter Automaton can exist for the language L={0i1i|i>=0}
a) true
b) false
490. • Let ∑={0,1}* and the grammar G be:
S->ε
S->SS
S->0S1|1S0
State which of the following is true for the given
a) Language of all and only Balanced strings
 b) It contains equal number of 0’s and 1’s
c) Ambiguous Grammar
d) All of the mentioned
491. • The instantaneous PDA is has the following elements
a) State
b) Unconsumed input
c) Stack content
d) All of the mentioned
492. • The moves in the PDA is technically termed as:
a) Turnstile
b) Shifter
c) Router
d) None of the mentioned
493. • Which of the following option resembles the given PDA?
Find the option which resembles the given PDA

a) {0n1n|n>=0}
b) {0n12n|n>=0}
c) {02n1n|n>=0}
d) None of the mentioned

494. • Which of the following correctly resembles the given state diagram?
The given state diagram resembles {wwr|w=(a+b)}

**a) {wwr|w=(a+b)}**
b) ε is called the initial stack symbol
c) All of the mentioned
d) None of the mentioned
495. • Which of the following assertion is false?
a) If L is a language accepted by PDA1 by final state, there exist a PDA2 that accepts
L by empty stack i.e. L=L(PDA1)=L(PDA2)
b) If L is a CFL then there exists a push down automata P accepting CF; by empty
stack i.e. L=M(P)
c) Let L is a language accepted by PDA1 then there exist a CFG X such that
L(X)=M(P)
d) All of the mentioned
496. • A push down automata can represented using:
a) Transition graph
b) Transition table
c) ID
d) All of the mentioned
497. • State true or false:
Statement: Every context free grammar can be transformed into an equvalent non
deterministic push down automata.
a) true
b) false
498. • Which of the following statement is false?
a) For non deterministic PDA, equivalence is undecidable
b) For deterministic PDA, equivalence is decidable
c) For deterministic PDA, equivalence is undecidable
d) None of the mentioned
499. • Which of the following are the actions that operates on stack top?
a) Pushing
b) Popping
c) Replacing
d) All of the mentioned
500. • A push down automata is said to be _________ if it has atmost one
transition around all configurations.
a) Finite
b) Non regular
c) Non-deterministic
d) Deterministic
501. • The transition a Push down automaton makes is additionally dependent
upon the:
a) stack
b) input tape
c) terminals
d) none of the mentioned
502. • A PDA machine configuration (p, w, y) can be correctly represented as:
a) (current state, unprocessed input, stack content)
b) (unprocessed input, stack content, current state)
c) (current state, stack content, unprocessed input)
d) none of the mentioned
503. • |-* is the __________ closure of |-
a) symmetric and reflexive
b) transitive and reflexive
c) symmetric and transitive
d) none of the mentioned
504. • With reference of a DPDA, which among the following do we perform from
the start state with an empty stack?
a) process the whole string
b) end in final state
c) end with an empty stack
d) all of the mentioned
505. • A DPDA is a PDA in which:
a) No state p has two outgoing transitions
b) More than one state can have two or more outgoing transitions
c) Atleast one state has more than one transitions
d) None of the mentioned
506. • State true or false:
Statement: For every CFL, G, there exists a PDA M such that L(G) = L(M) and vice
versa.
a) true
b) false
507. • If the PDA does not stop on an accepting state and the stack is not empty,
the string is:
a) rejected
b) goes into loop forever
c) all of the mentioned
d) none of the mentioned
508. • A language accepted by Deterministic Push down automata is closed under
which of the following?
a) Complement
b) Union
c) All of the mentioned
d) None of the mentioned
509. • Which of the following is a simulator for non deterministic automata?
a) JFLAP
b) Gedit
c) FAUTO
d) None of the mentioned
510. • Finite-state acceptors for the nested words can be:
a) nested word automata
b) push down automata
c) ndfa
d) none of the mentioned
511. • Which of the following is analogous to the following?
:NFA and NPDA
a) Regular language and Context Free language
b) Regular language and Context Sensitive language
c) Context free language and Context Sensitive language
d) None of the mentioned
512. • Let T={p, q, r, s, t}. The number of strings in S* of length 4 such that no
symbols can be repeated.
a) 120
b) 625
c) 360
d) 36
513. • Which of the following relates to Chomsky hierarchy?
a) Regular < CFL < CSL < Unrestricted
b) CFL < CSL < Unrestricted < Regular
c) CSL < Unrestricted < CF < Regular
d) None of the mentioned
514. • A language is accepted by a push down automata if it is:
a) regular
b) context free
c) regular and context free
d) none of the mentioned
515. • Which of the following is an incorrect regular expression identity?
a) R+f=R
b) eR=e
c) Rf=f
d) None of the mentioned
516. • Which of the following strings do not belong the given regular expression?
(a)*(a+cba)
a) aa
b) aaa
c) acba
d) acbacba
517. • Which of the following regular expression allows strings on {a,b}* with
length n where n is a multiple of 4.
a) (a+b+ab+ba+aa+bb+aba+bab+abab+baba)*
b) (bbbb+aaaa)*
c) *((a+b)(a+b)(a+b)(a+b))
d) None of the mentioned
518. • Which of the following strings is not generated by the given grammar:
S->SaSbS|e
a) aabb
b) abab
c) abaabb
d) None of the mentioned
519. • abb*c denotes which of the following?
a) {abnc|n=0}
b) {abnc|n=1}
c) {anbc|n=0}
d) {abcn|n>0}
520. • The following denotion belongs to which type of language:
G=(V, T, P, S)
a) Regular grammar
b) Context free grammar
c) Context Sensitive grammar
d) All of the mentioned

1. Context free grammar is called Type 2 grammar because of ______________

hierarchy.
a) Greibach
b) Backus
c) Chomsky
d) None of the mentioned
2. a→b
Restriction: Length of b must be atleast as much length of a.
Which of the following is correct for the given assertion?
a) Greibach Normal form
b) Context Sensitive Language
c) Chomsky Normal form
d) Recursively Ennumerable language
3. From the definition of context free grammars,
G=(V, T, P, S)
What is the solution of VÇT?
a) Null
b) Not Null
c) Cannot be determined, depends on the language
d) None of the mentioned
4. If P is the production, for the given statement, state true or false.
P: V->(V∑T)* represents that the left hand side production rule has no right or left
context.
a) true
b) false
5. There exists a Context free grammar such that:
X->aX
Which among the following is correct with respect to the given assertion?
a) Left Recursive Grammar
b) Right Recursive Grammar
c) Non Recursive Grammar
d) None of the mentioned
6. If the partial derivation tree contains the root as the starting variable, the form is
known as:
a) Chomsky hierarchy
b) Sentential form
c) Root form
d) None of the mentioned
 7. Find a regular expression for a grammar which generates a language which states :
L contains a set of strings starting with an a and ending with a b, with something in
the middle.
a) a(aUb)b
b) a*(aUb)b*
c) a(ab)b
d) None of the mentioned
8. Which of the following is the correct representation of grammar for the given regular
expression?
a(aUb)*b
a)
(1) S → aMb
(2) M → e
(3) M → aM
(4) M → bM

b)
(1) S → aMb
(2) M → Mab
(3) M → aM
(4) M → bM

c)
(1) S → aMb
(2) M → e
(3) M → aMb
(4) M → bMa

d) None of the mentioned

9. A CFG consist of the following elements:

a) a set of terminal symbols
b) a set of non terminal symbols
c) a set of productions
d) all of the mentioned
10. A CFG for a program describing strings of letters with the word “main” somewhere in
the string:
a)
-> m a i n
-> | epsilon
-> A | B | ... | Z | a | b ... | z

b)
--> m a i n
-->

--> A | B | ... | Z | a | b ... | z

c)
--> m a i n
--> | epsilon
--> A | B | ... | Z | a | b ... | z

d) None of the mentioned

521. • CFGs are more powerful than:

a) DFA
b) NDFA
c) Mealy Machine
d) All of the mentioned
522. • State true or false:
S-> 0S1|01
Statement: No regular expression exists for the given grammar.
a) true
b) false
523. • For the given set of code, the grammar representing real numbers in Pascal
has error in one of the six lines. Fetch the error.
(1) ->
(2) -> | epsilon
(3) -> | epsilon
(4) -> ‘E’ | epsilon
(5) -> + | – | epsilon
(6) -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
a) 3
b) 4
c) 2
d) No errors
524. • Which among the following is incorrect with reference to a derivation tree?
a) Every vertex has a label which is a terminal or a variable.
b) The root has a label which can be a terminal.
c) The label of the internal vertex is a variable.
d) None of the mentioned
525. • Let G=(V, T, P, S)
where a production can be written as:
S->aAS|a
A->SbA|ba|SS
Which of the following string is produced by the grammar?
a) aabbaab
b) aabbaa
c) baabab
d) None of the mentioned
526. • Statement 1: Ambiguity is the property of grammar but not the language.
Statement 2: Same language can have more than one grammar.
Which of the following options are correct with respect to the given statements?
a) Statement 1 is true but statement 2 is false
b) Statement 1 is false but statement 2 is true
c) Both the statements are true
d) Both the statements are false
527. • Which of the following are non essential while simplifying a grammar?
a) Removal of useless symbols
b) Removal of unit productions
c) Removal of null production
d) None of the mentioned
528. • Which of the following are context free language?
a) L={aibi|i>=0}
b) L={wwr| w is a string and r represents reverse}
c) All of the mentioned
d) one of the mentioned
529. • The language L ={ai2bi|i>=0} is:
a) recursive
b) deterministic CFL
c) regular
d) Two of the mentioned is correct
530. • L->rLt|tLr|t|r
The given grammar produces a language which is:
a) All palindrome
b) All even palindromes
c) All odd palindromes
d) Strings with same begin and end symbols
531. • Suppose A->xBz and B->y, then the simplified grammar would be:
a) A->xyz
b) A->xBz|xyz
c) A->xBz|B|y
d) none of the mentioned
532. • Given Grammar: S->A, A->aA, A->e, B->bA
Which among the following productions are Useless productions?
a) S->A
b) A->aA
c) A->e
d) B->bA
533. • Given:
S->…->xAy->…->w
if ____________, then A is useful, else useless symbol.
a) A is a non terminal
b) A is a terminal
c) w ∈ L
d) w ∉ L
534. • Given:
S->aSb
S->e
S-> A
A->aA
B->C
C->D
The ratio of number of useless variables to number of useless production is:
a) 1
b) 3/4
 c) 2/3
d) 0
535. • Given grammar G:
S->aS|A|C
A->a
B->aa
C->aCb
Find the set of variables that can produce strings only with the set of terminals.
a) {C}
b) {A,B}
c) {A,B,S}
d) None of the mentioned
536. • Given grammar:
S->aS|A
A->a
B->aa
Find the number of variables reachable from the Starting Variable?
a) 0
b) 1
c) 2
d) None of the mentioned
537. • In order to simplify a context free grammar, we can skip the following
operation:
a) Removal of null production
b) Removal of useless symbols
c) Removal of unit productions
d) None of the mentioned
538. • Given a Grammar G:
S->aA
A->a
A->B
B->A
B->bb
Which among the following will be the simplified grammar?
a) S->aA|aB, A->a, B->bb
b) S->aA|aB, A->B, B->bb
c) S->aA|aB, A->a, B->A
d) None of the mentioned
539. • Simplify the given grammar:
A-> a| aaA| abBc
B-> abba| b
a) A-> a| aaA| ababbAc| abbc
b) A-> a| aaA| ababbAc| abbc, B-> abba|b
c) A-> a| aaA| abbc, B->abba
d) None of the mentioned
540. • In context to the process of removing useless symbols, which of the
following is correct?
a) We remove the Nullable variables
b) We eliminate the unit productions
c) We eliminate productions which yield no terminals
d) All of the mentioned
541. • The use of variable dependency graph is in:
a) Removal of useless variables
b) Removal of null productions
c) Removal of unit productions
d) None of the mentioned
542. • The variable which produces an epsilon is called:
a) empty variable
b) nullable
c) terminal
d) all of the mentioned
543. • Statement:
For A-> e ,A can be erased. So whenever it appears on the left side of a production,
replace with another production without the A.
State true or false:
a) true
b) false
544. • Simplify the given grammar:
S->aXb
X->aXb | e
a) S->aXb | ab, X-> aXb | ab
b) S->X | ab, X-> aXb | ab
c) S->aXb | ab, X-> S | ab
d) None of the mentioned
545. • Consider the following grammar:
A->e
B->aAbC
B->bAbA
A->bB
The number of productions added on the removal of the nullable in the given
grammar:
a) 3
b) 4
c) 2
d) 0
546. • Let G=(V, T, P, S) be a CFG such that _____________. Then there exists
an equivalent grammar G’ having no e productions.
a) e ∈ L(G)
b) w ∉ L(G)
c) e ∉ L(G)
d) w ∈ L(G)
547. • For each production in P of the form:
A-> x1x2x3…xn
put into P’ that production as well as all those generated by replacing null variables
with e in all possible combinations. If all x(i) are nullable,
a) A->e is put into P’
b) A->e is not put into P’
c) e is a member of G’
d) None of the mentioned
548. • For the given grammar G:
S->ABaC
A->BC
B->b| e
C->D| e
D-> d
Remove the e productions and generate the number of productions from S in the
modified or simplified grammar.
a) 6
b) 7
c) 5
d) 8
549. • Consider G=({S,A,B,E}, {a,b,c},P,S), where P consists of S →AB, A →a,
B →b and E →c.
Number of productions in P’ after removal of useless symbols:
a) 4
b) 3
c) 2
d) 5
550. • Given grammar G:
S->aS| AB
A-> e
B-> e
D-> b
Reduce the grammar, removing all the e productions:
a) S->aS| AB| A| B, D-> b
b) S->aS| AB| A| B| a, D-> b
c) S->aS| AB| A| B
d) None of the mentioned
551. • Which of the following is the format of unit production?
a) A->B
b) A->b
c) B->Aa
d) None of the mentioned
552. • Given Grammar G:
S->aA
A->a| A
B->B
The number of productions to be removed immediately as Unit productions:
a) 0
b) 1
 c) 2
d) 3
553. • Given grammar:
S->aA
A->a
A->B
B-> A
B->bb
Which of the following is the production of B after simplification by removal of unit
productions?
a) A
b) bb
c) aA
d) A| bb
554. • If grammar G is unambiguous, G’ produced after the removal of Unit
production will be:
a) ambiguous
b) unambiguous
c) finite
d) cannot be said
555. • If C is A-derivable, C->B is a production, and B ≠ A, then B is
a) nullable
b) Non-derivable
c) A-derivable
d) None of the mentioned
556. • A can be A-> derivable if and only if __________
a) A-> A is actually a production
b) A->B, B-> A exists
c) All of the mentioned
d) None of the mentioned
557. • Given Grammar:
T-> T+R| R
R-> RV| V
V->(T)| u
When unit productions are deleted we are left with
T-> T+R| _______|(T)| u
R->RV|(T)| u
V-> (T)| u
Fill in the blank:
a) TV
b) T+V
c) RT
d) R*V
558. • Given grammar G:
S-> ABA, A->aA|e, B-> bB|e
Eliminate e and unit productions. State the number of productions the starting variable
holds?
a) 6
b) 7
 c) 9
d) 5
559. • Given grammar G:
S-> A| B| C
A-> aAa| B
B-> bB|bb
C->aCaa|D
D->baD|abD|aa
Eliminate e and unit productions and state the number of variables left?
a) 5
b) 4
c) 3
d) 2
560. • Which of the following variables in the given grammar is called live
variable?
S->AB
A->a
a) S
b) A
c) B
d) None of the mentioned
561. • The format: A->aB refers to which of the following?
a) Chomsky Normal Form
b) Greibach Normal Form
c) Backus Naur Form
d) None of the mentioned
562. • Which of the following does not have left recursions?
a) Chomsky Normal Form
b) Greibach Normal Form
c) Backus Naur Form
d) All of the mentioned
563. • Every grammar in Chomsky Normal Form is:
a) regular
b) context sensitive
c) context free
d) all of the mentioned
564. • Which of the production rule can be accepted by Chomsky grammar?
a) A->BC
b) A->a
c) S->e
d) All of the mentioned
565. • Given grammar G:
(1)S->AS
(2)S->AAS
(3)A->SA
(4)A->aa
Which of the following productions denies the format of Chomsky Normal Form?
a) 2,4
b) 1,3
 c) 1, 2, 3, 4
d) 2, 3, 4
566. • Which of the following grammars are in Chomsky Normal Form:
a) S->AB|BC|CD, A->0, B->1, C->2, D->3
b) S->AB, S->BCA|0|1|2|3
c) S->ABa, A->aab, B->Ac
d) All of the mentioned
567. • With reference to the process of conversion of a context free grammar to
CNF, the number of variables to be introduced for the terminals are:
S->ABa
A->aab
B->Ac
a) 3
b) 4
c) 2
d) 5
568. • In which of the following, does the CNF conversion find its use?
a) CYK Algorithm
b) Bottom up parsing
c) Preprocessing step in some algorithms
d) All of the mentioned
569. • Let G be a grammar. When the production in G satisfy certain restrictions,
then G is said to be in ___________
a) restricted form
b) parsed form
c) normal form
d) all of the mentioned
570. • Let G be a grammar: S->AB|e, A->a, B->b
Is the given grammar in CNF?
a) Yes
b) No
571. • Which of the following is called Bar-Hillel lemma?
a) Pumping lemma for regular language
b) Pumping lemma for context free languages
c) Pumping lemma for context sensitive languages
d) None of the mentioned
572. • Which of the expressions correctly is an requirement of the pumping lemma
for the context free languages?
a) uvnwxny
b) uvnwnxny
c) uv2nwx2ny
d) All of the mentioned
573. • Let L be a CFL. Then there is an integer n so that for any u that belong to
language L satisfying |t|≥n, there are strings u, v, w, x, y and z satisfying t=uvwxy.
Let p be the number of variables in CNF form of the context free grammar. The value
of n in terms of p is
a) 2p
b) 2p
c) 2p+1
d) p²
574. • Which of the following gives a positive result to the pumping lemma
restrictions and requirements?
a) {aibici|i≥0}
b) {0i1i|i≥0}
c) {ss|s∈{a,b}*}
d) None of the mentioned
575. • Using pumping lemma, which of the following cannot be proved as ‘not a
CFL’?
a) {aibici|i≥0}
b) {ss|s∈{a,b}*}
c) The set legal C programs
d) None of the mentioned
576. • State true or false:
Statement: We cannot use Ogden’s lemma when pumping lemma fails.
a) true
b) false
577. • Which of the following cannot be filled in the blank below?
Statement: There are CFLs L1 and L2 so that ___________is not a CFL.
a) L1∩L2
b) L1′
c) L1*
d) None of the mentioned
578. • The pumping lemma is often used to prove that a language is:
a) Context free
b) Not context free
c) Regular
d) None of the mentioned
579. • What is the pumping length of string of length x?
a) x+1
b) x
c) x-1
d) x²
580. • Which of the following does not obey pumping lemma for context free
languages?
a) Finite languages
b) Context free languages
c) Unrestricted languages
d) None of the mentioned
581. • The context free languages are closed under:
a) Intersection
b) Complement
c) Kleene
d) None of the mentioned
582. • Given Grammar G1:
S->aSb
S->ε
Grammar G2:
R->cRd
R->ε
 If L(G) = L(G1) ∪ L(G2), the number of productions the new starting variable would
have:
a) 2
b) 3
c) 4
d) 1
583. • Context free languages are not closed under:
a) Intersection
b) Intersection with Regular Language
c) Complement
d) All of the mentioned
584. • Which of the following is incorrect?
There exists algorithms to decide if:
a) String w is in CFL L
b) CFL L is empty
c) CFL L is infinite
d) All of the mentioned
585. • If the start symbol is one of those symbols which produce no terminal
through any sequence, the CFL is said to be
a) nullable
b) empty
c) eliminated
d) none of the mentioned
586. • Using the pumping constant n, If there is a string in the language of length
between _____ and ____ then the language is infinite else not.
a) n, 2n-1
b) 2n, n
c) n+1, 3n+6
d) 0, n+1
587. • Which of the following is/are CFL not closed under?
a) Reverse
b) Homomorphism
c) Inverse Homomorphism
d) All of the mentioned
588. • If L1 and L2 are context free languages, L1-L2 are context free:
a) always
b) sometimes
c) never
d) none of the mentioned
589. • A___________ is context free grammar with at most one non terminal in
the right hand side of the production.
a) linear grammar
b) linear bounded grammar
c) regular grammar
d) none of the mentioned
590. • There is a linear grammar that generates a context free grammar
a) always
b) never
c) sometimes
d) none of the mentioned
591. • The following format of grammatical notation is accepted by which of the
following:
AB -> CD
A -> BC or
A -> B or
A -> a
where A, B, C, D are non terminal symbols and a is a terminal symbol.
a) Greibach Normal Form
b) Chomsky Normal Form
c) Kuroda Normal Form
d) None of the mentioned
592. • Every Kuroda Normal form grammar generates ___________
a) Context free grammar
b) Context sensitive grammar
c) Unrestricted grammar
d) None of the mentioned
593. • Which of the following can generate Unrestricted grammars?
a) Pentonnen Normal form
b) Floyd Normal form
c) Greibach Normal form
d) None of the mentioned
594. • Given a grammar in GNF and a derivable string in the grammar with the
length n, any ___________ will halt at depth n.
a) top-down parser
b) bottom-up parser
c) multitape turing machine
d) none of the mentioned
595. • Which of the following grammars is similar to Floyd Normal form?
a) Backus Naur Form
b) Kuroda Normal Form
c) Greibach Normal Form
d) Chomsky Normal Form
596. • Which among the following can parse a context free grammar?
a) top down parser
b) bottom up parser
c) CYK algorithm
d) all of the mentioned
597. • The standard version of CYK algorithm operates only on context free
grammars in the following form:
a) Greibach Normal form
b) Chomsky Normal form
c) Backus Naur form
d) All of the mentioned
598. • The __________ running time of CYK is O(n³ · |G|) where n is the length of
the parse string and |G| is the size of the context free grammar G.
a) worst
b) best
c) average
d) none of the mentioned
599. • Which of the following is true for Valiants algorithm?
a) an extension of CYK
b) deals with efficient multiplication algorithms
c) matrices with 0-1 entries
d) all of the mentioned
600. • Which among the following is a correct option in format for representing
symbol and expression in Backus normal form?
a) <symbol> ->expression
b) <symbol>::=expression
c) <symbol>=<expression>
d) all of the mentioned
601. • Which of the following is not a negative property of Context free
languages?
a) Intersection
b) Complement
c) Intersection and Complement
d) None of the mentioned
602. • The intersection of context free language and regular language is
_________
a) regular language
b) context free language
c) context sensitive language
d) none of the mentioned
603. • Which of the following is regular?
a) a100b100
b) (a+b) - {a100b100}*
c) a100b100 and (a+b)* - {a100b100}
d) None of the mentioned
604. • Which of the following is not context free?
a) {w: nA = nB = nC}
b) {abc*}
c) {a100b100}
d) All of the mentioned
605. • Which of the following can be used to prove a language is not context free?
a) Ardens theorem
b) Power Construction method
c) Regular Closure
d) None of the mentioned
606. • Which of the following are valid membership algorithms?
a) CYK algorithm
b) Exhaustive search parser
c) CYK algorithm and Exhaustive search parser
d) None of the mentioned
607. • Which of the following belong to the steps to prove emptiness?
a) Remove useless variable
b) Check if a start variable S is useless
c) Remove useless variable and Check if a start variable S is useless
d) None of the mentioned
608. • Which of the following is true for CYK Algorithm?
a) Triangular Table
b) Circular Chart
c) Linked List
d) None of the mentioned
609. • Which of the following steps are wrong with respect to infiniteness
problem?
a) Remove useless variables
b) Remove unit and epsilon production
c) Create dependency graph for variables
d) If there is a loop in the dependency graph the language is finite else infinite
610. • State true or false:
Statement: Every context free language can be generated by a grammar which
contains no useless non terminals.
a) true
b) false
611. • A turing machine is a
a) real machine
b) abstract machine
c) hypothetical machine
d) more than one option is correct
612. • A turing machine operates over:
a) finite memory tape
b) infinite memory tape
c) depends on the algorithm
d) none of the mentioned
613. • Which of the functions are not performed by the turing machine after
reading a symbol?
a) writes the symbol
b) moves the tape one cell left/right
c) proceeds with next instruction or halts
d) none of the mentioned
614. • ‘a’ in a-machine is :
a) Alan
b) arbitrary
c) automatic
d) None of the mentioned
615. • Which of the problems were not answered when the turing machine was
invented?
a) Does a machine exists that can determine whether any arbitrary machine on its tape
is circular.
b) Does a machine exists that can determine whether any arbitrary machine on its tape
is ever prints a symbol
c) Hilbert Entscheidungs problem
d) None of the mentioned
616. • The ability for a system of instructions to simulate a Turing Machine is
called _________
a) Turing Completeness
b) Simulation
c) Turing Halting
d) None of the mentioned
617. • Turing machine can be represented using the following tools:
a) Transition graph
b) Transition table
c) Queue and Input tape
d) All of the mentioned
618. • Which of the following is false for an abstract machine?
a) Turing machine
b) theoretical model of computer
c) assumes a discrete time paradigm
d) all of the mentioned
619. • Fill in the blank with the most appropriate option.
Statement: In theory of computation, abstract machines are often used in
___________ regarding computability or to analyze the complexity of an algorithm.
a) thought experiments
b) principle
c) hypothesis
d) all of the mentioned
620. • State true or false:
Statement: RAM model allows random access to indexed memory locations.
a) true
b) false
621. • A turing machine that is able to simulate other turing machines:
a) Nested Turing machines
b) Universal Turing machine
c) Counter machine
d) None of the mentioned
622. • Which of the problems are unsolvable?
a) Halting problem
b) Boolean Satisfiability problem
c) Halting problem & Boolean Satisfiability problem
d) None of the mentioned
623. • Which of the following a turing machine does not consist of?
a) input tape
b) head
c) state register
d) none of the mentioned
624. • The value of n if turing machine is defined using n-tuples:
a) 6
b) 7
c) 8
d) 5
625. • If d is not defined on the current state and the current tape symbol, then the
machine ______
a) does not halts
b) halts
c) goes into loop forever
d) none of the mentioned
626. • Statement: Instantaneous descriptions can be designed for a Turing
machine.
State true or false:
a) true
b) false
627. • Which of the following are the models equivalent to Turing machine?
a) Multi tape turing machine
b) Multi track turing machine
c) Register machine
d) All of the mentioned
628. • Which among the following is incorrect for o-machines?
a) Oracle Turing machines
b) Can be used to study decision problems
c) Visualizes Turing machine with a black box which is able to decide cerain decion
problems in one operation
d) None of the mentioned
629. • RASP stands for:
a) Random access storage program
b) Random access stored program
c) Randomly accessed stored program
d) Random access storage programming
630. • Which of the following is not true about RASP?
a) Binary search can be performed more quickly using RASP than a turing machine
b) Stores its program in memory external to its state machines instructions
c) Has infinite number of distinguishable, unbounded registers
d) Binary search can be performed less quickly using RASP than a turing
machine
e) More than two options are incorrect
631. • State true or false:
Statement: RASP is to RAM like UTM is to turing machine.
a) true
b) false
632. • The class of recursively enumerable language is known as:
a) Turing Class
b) Recursive Languages
c) Universal Languages
d) RE
633. • A language L is said to be Turing decidable if:
a) recursive
b) TM recognizes L
c) TM accepts L
d) recursive & TM recognizes L
634. • Which of the following statements are false?
a) Every recursive language is recursively enumerable
b) Recursively enumerable language may not be recursive
c) Recursive languages may not be recursively enumerable
d) None of the mentioned
635. • Choose the correct option:
Statement: If L1 and L2 are recursively enumerable languages over S, then the
following is/are recursively enumerable.
a) L1 U L2
b) L2 ∩ L2
c) Both L1 U L2 and L2 ∩ L2
d) None of the mentioned
636. • If L is a recursive language, L’ is:
a) Recursive
b) Recursively Enumerable
c) Recursive and Recursively Enumerable
d) None of the mentioned
637. • Choose the appropriate option:
Statement: If a language L is recursive, it is closed under the following operations:
a) Union
b) Intersection
c) Complement
d) All of the mentioned
638. • A recursively enumerable language L can be recursive if:
a) L’ is recursively enumerable
b) Every possible sequence of moves of T, the TM which accept L, causes it to halt
c) L’ is recursively enumerable and every possible sequence of moves of T, the
TM which accept L, causes it to halt
d) None of the mentioned
639. • A language L is recursively enumerable if L=L(M) for some turing machine
M.
Language L is recursively enumerable if L=L(M) for some turing machine M
Which among the following cannot be among A, B and C?

a) yes w ∈ L
b) no w ∉ L
c) M does not halt w ∉ L
d) None of the mentioned
640. • State true or false:
Statement: An enumerator is a turing machine with extra output tape T, where
symbols, once written, are never changed.
a) true
b) false
641. • A Language L may not be accepted by a Turing Machine if:
a) It is recursively enumerable
b) It is recursive
c) L can be enumerated by some turing machine
d) None of the mentioned
642. • Which of the following regular expression resembles the given diagram?
The given diagram is a transition graph for a turing machine

a) {a}{b}{a,b}
b) {a,b}{aba}
c) {a,b}{bab}
d) {a,b}{a}{b}*

643. • Construct a turing machine which accepts a string with ‘aba’ as its
substring.
a)The turing machine which accepts a string with ‘aba’ as its substring - option a
b)The turing machine which accepts a string with ‘aba’ as its substring - option b
c)The turing machine which accepts a string with ‘aba’ as its substring - option c
d)The turing machine which accepts a string with ‘aba’ as its substring - option
644. • The number of states required to automate the last question i.e.
{a,b}{aba}{a,b} using finite automata:
a) 4
b) 3
c) 5
d) 6
645. • The machine accept the string by entering into hA or it can:
a) explicitly reject x by entering into hR
b) enter into an infinte loop
c) explicitly reject x by entering into hR and enter into an infinte loop
d) None of the mentioned
646. • d(q,X)=(r,Y,D) where D cannot be:
D is direction in which automata moves forward as per the queue

a) L
b) R
c) S
d) None of the mentioned

647. • Which of the following can accept even palindrome over {a,b}
a) Push down Automata
b) Turing machine
c) NDFA
d) All of the mentioned
648. • Which of the functions can a turing machine not perform?
a) Copying a string
b) Deleting a symbol
c) Accepting a pal
d) Inserting a symbol
649. • If T1 and T2 are two turing machines. The composite can be represented
using the expression:
a) T1T2
b) T1 U T2
c) T1 X T2
d) None of the mentioned
650. • The following turing machine acts like:
The turing machine acts like Delete a symbol

a) Copies a string
b) Delete a symbol
c) Insert a symbol
d) None of the mentioned
 651. • What does the following transition graph shows:
The composite TM accepts the language of palindromes over {a, b}

a) Copies a symbol
b) Reverses a string
c) Accepts a pal
d) None of the mentioned

Finite Automata & Regular Languages

1. Which of the following languages is regular?

o a) {a^n b^n | n ≥ 0}
o b) {w | w contains an equal number of a's and b's}
o c) {w | w contains at least one 'a'}
o d) {w | w contains an equal number of 'a's and 'b's, and 'c's}
2. The pumping lemma is used to prove that a language is:
o a) Context-free
o b) Regular
o c) Not regular
o d) Context-sensitive
3. Which of the following is not closed under union?
o a) Regular languages
o b) Context-sensitive languages
o c) Context-free languages
o d) Recursively enumerable languages
4. The language {a^n b^n c^n | n ≥ 0} is:
o a) Regular
o b) Context-free
o c) Context-sensitive
o d) Not recursively enumerable
5. Which of the following regular expressions represents the language of strings
containing an even number of 'a's?
o a) (aa)*
o b) (a* b*)*
o c) (aa | a) b**
o d) (a | b)*
6. The intersection of two regular languages is:
 o a) Regular
o b) Context-free
o c) Regular
o d) Context-sensitive
7. Which of the following is not a valid DFA?
o a) A machine with no final states
o b) A machine with multiple initial states
o c) A machine with ε-transitions
o d) A machine with exactly one initial state
8. The minimum number of states in a DFA that accepts the language {w | w
contains an even number of 'a's and an odd number of 'b's} is:
o a) 2
o b) 3
o c) 4
o d) 5
9. Which of the following languages is not regular?
o a) {a^n b^n | n ≥ 0}
o b) {w | w contains an equal number of 'a's and 'b's}
o c) {a^n b^n c^n | n ≥ 0}
o d) {w | w contains at least one 'a'}
10. The language {a^n b^n | n ≥ 0} is:
o a) Regular
o b) Context-free
o c) Context-sensitive
o d) Not recursively enumerable

Context-Free Grammars & Pushdown Automata

11. Which of the following grammars is context-free?

o a) S → aSb | ε
o b) S → aSbS | ε
o c) S → aSb | bSa | ε
o d) S → aSbS | bSaS | ε
12. The language generated by the grammar S → aSb | ε is:
o a) {a^n b^n | n ≥ 0}
o b) {a^n b^n | n ≥ 0}
o c) {a^n b^n c^n | n ≥ 0}
o d) {w | w contains an equal number of 'a's and 'b's}
13. Which of the following is not a context-free language?
o a) {a^n b^n | n ≥ 0}
o b) {a^n b^n c^n | n ≥ 0}
o c) {a^n b^n c^n | n ≥ 0}
o d) {w | w contains an equal number of 'a's and 'b's}
14. The language {a^n b^n c^n | n ≥ 0} is:
o a) Regular
o b) Context-free
o c) Context-sensitive
o d) Not recursively enumerable
 15. Which of the following is not a valid context-free grammar?
o a) S → aSb | ε
o b) S → aSbS | ε
o c) S → aSbS | bSaS | ε
o d) S → aSb | bSa | ε
16. The language {a^n b^n c^n | n ≥ 0} is:
o a) Regular
o b) Context-free
o c) Context-sensitive
o d) Not recursively enumerable
17. Which of the following is not a context-free language?
o a) {a^n b^n | n ≥ 0}
o b) {a^n b^n c^n | n ≥ 0}
o c) {a^n b^n c^n | n ≥ 0}
o d) {w | w contains an equal number of 'a's and 'b's}
18. The language {a^n b^n | n ≥ 0} is:
o a) Regular
o b) Context-free
o c) Context-sensitive
o d) Not recursively enumerable
19. Which of the following is not a valid context-free grammar?
o a) S → aSb | ε
o b) S → aSbS | ε
o c) S → aSbS | bSaS | ε
o d) S → aSb | bSa | ε
20. The language {a^n b^n | n ≥ 0} is:
o a) Regular
o b) Context-free
o c) Context-sensitive
o d) Not recursively enumerable

Turing Machines & Decidability

21. Which of the following is not a Turing machine?

o a) A machine that can simulate any algorithm
o b) A machine that can decide any algorithm
o c) A machine that can compute any algorithm
o d) A machine that can recognize any algorithm
22. The language {a^n b^n | n ≥ 0} is:
o a) Regular
o b) Context-free
o c) Context-sensitive
o d) Not recursively enumerable
23. Which of the following is not a valid Turing machine?
o a) A machine that can simulate any algorithm
o b) A machine that can decide any algorithm
o c) A machine that can compute any algorithm
o d) A machine that can recognize any algorithm
24. The language {a^n b^n | n ≥ 0} is:
o a) Regular
o b) Context-free
o c) Context-sensitive
o d) Not recursively enumerable
25. Which of the following is not a Turing machine?
o a) A machine that can simulate any algorithm
o b) A machine that can decide any algorithm
o c) A machine that can compute any algorithm
o d) A machine that can recognize any algorithm
26. The language {a^n b^n | n ≥ 0} is:
o a) Regular
o b) Context-free
o c) Context-sensitive
o d) Not recursively enumerable
27. Which of the following is not a valid Turing machine?
o a) A machine that can simulate any algorithm
o b) A machine that can decide any algorithm
o c) A machine that can compute any algorithm
o d) A machine that can recognize any algorithm
28. The language {a^n b^n | n ≥ 0} is:
o a) Regular
o b) Context-free
o c) Context-sensitive
o d) Not recursively enumerable
29. Which of the following is not a Turing machine?
o a) A machine that can simulate any algorithm
o b) A machine that can decide any algorithm
o c) A machine that can compute any algorithm
o d) A machine that can recognize any algorithm
30. The language {a^n b^n | n ≥ 0} is:
o a) Regular
o b) Context-free
o c) Context-sensitive
o d) Not recursively enumerable
31. • Which of the following languages is not accepted by any finite automaton?
a) {w | w contains an even number of 0’s}
b) {a^n b^n | n ≥ 0}
32. • The state complexity of the minimal DFA accepting all strings over {0,1} that end
with "101" is:
a) 3
b) 4
33. • Which of the following operations does not preserve regularity?
a) Union
b) Concatenation
c) Intersection with a context-free language
34. • The language generated by the grammar S → aSb | ab is:
a) {a^n b^m | n, m ≥ 1}
b) {a^n b^n | n ≥ 1}
35. • Which of the following is true for deterministic pushdown automata (DPDA)?
a) DPDA can accept all context-free languages
b) DPDA accept a strict subset of CFLs
36. • The emptiness problem for a Turing machine is:
a) Decidable
b) Undecidable
37. • Which of the following is true for the language L = {ww | w ∈ {0,1}*}?
a) L is regular
b) L is not context-free
38. • The halting problem is:
a) Decidable for all Turing machines
b) Undecidable
39. • The equivalence problem for two DFAs is:
a) Undecidable
b) Decidable
40. • The pumping lemma for context-free languages helps to:
a) Prove that a language is context-free
b) Prove that a language is not context-free
41. • Which of the following is not true about Turing machines?
a) They can simulate any algorithm
b) They have limited memory
42. • The complement of a context-free language is:
a) Always context-free
b) Not necessarily context-free
43. • The union of two context-free languages is:
a) Always regular
b) Always context-free
44. • The language L = {a^i b^j c^k | i, j, k ≥ 0 and i = j or j = k} is:
a) Regular
b) Context-free
45. • The Chomsky hierarchy has how many types of grammars?
a) 3
b) 4
46. • A language is recursive if:
a) There exists a Turing machine that halts and accepts all strings in the language
b) There exists a Turing machine that halts on all inputs and accepts strings in
the language
47. • The set of all strings over {0,1} with an equal number of 0’s and 1’s is:
a) Regular
b) Not regular
48. • Which of the following is true for the DFA minimization problem?
a) It is undecidable
b) There exists a polynomial time algorithm
49. • Which of the following problems is undecidable?
a) Membership problem for regular languages
b) Equivalence problem for Turing machines
50. • Which of the following statements is true?
a) All context-sensitive languages are recursive
b) All recursive languages are context-sensitive
Sample MCQ now….
1. In a Moore machine, the output function is associated with:
a) Transitions between states
b) States themselves
2. A Mealy machine produces output based on:
a) States
b) Transitions
3. Moore and Mealy machines are:
a) Different in computational power
b) Equivalent and can simulate each other
4. Which is NOT part of a finite automaton 5-tuple?
a) Final states
b) Output function λ
5. At any time, a DFA is in:
a) Multiple states
b) Exactly one state
6. Kleene star (Σ*) includes:
a) Only strings of length 1
b) All strings including empty string (ε)
7. An NFA differs from a DFA because:
a) Each transition is deterministic
b) It can be in multiple states at once
8. ε-NFAs allow:
a) No ε-transitions
b) Transitions without consuming input
9. Subset construction converts:
a) DFA to NFA
b) NFA to DFA
10. A DFA that accepts strings ending with "01" recognizes:
a) Strings starting with "01"
b) Strings with suffix "01"
11. Regular languages are generated by:
a) Type-2 grammars
b) Type-3 grammars
12. The start state of a finite automaton is:
a) Arbitrarily chosen
b) Where computation begins
13. The empty language Ø is:
a) Contains only empty string ε
b) Contains no strings
14. The transition function δ maps:
a) States to outputs
b) State and input symbol to next state
15. In a Mealy machine, output is produced:
a) Only at final states
b) On transitions
16. The finite automaton is represented as:
a) (Q, Σ, δ, λ, F)
b) (Q, Σ, δ, q0, F)
17. An NFA accepts a string if:
a) All paths lead to a final state
b) At least one path leads to a final state
18. Which is TRUE about NFAs and DFAs?
a) NFAs accept more languages
b) Both recognize the same languages
19. A dead state in a finite automaton is:
a) A state with no transitions
b) A trap state with no acceptance
20. The Chomsky hierarchy includes how many grammar types?
a) Two
b) Four
21. • A Context-Free Grammar (CFG) is in Chomsky Normal Form (CNF) if all
productions are of the form:
a) A → terminal followed by non-terminal
b) A → two non-terminals or a single terminal
22. • In Greibach Normal Form (GNF), every production starts with:
a) A non-terminal
b) A single terminal followed by zero or more non-terminals
23. • The first step in converting CFG to GNF is to:
a) Eliminate unit productions
b) Eliminate the start symbol from the right-hand side
24. • Useless productions in CFG are those that:
a) Never appear on the left side of any production
b) Cannot derive any terminal string
25. • A nullable variable in CFG is one that:
a) Cannot appear in any production
b) Can derive the empty string ε
26. • Unit productions are of the form:
a) A → α, where α is a string of terminals and non-terminals
b) A → B, where both A and B are non-terminals
27. • The elimination of ε-productions means removing productions that:
a) Produce a single terminal
b) Produce the empty string ε
28. • The parse tree root node always represents:
a) A terminal symbol
b) The start symbol
29. • Ambiguity in CFG means:
a) The grammar generates no strings
b) A string has more than one distinct parse tree
30. • The leftmost derivation always substitutes:
a) The rightmost variable first
b) The leftmost variable first
31. • According to Arden’s theorem, the solution for R = Q + RP is:
a) R = Q + P*
b) R = QP*
32. • Regular expressions are equivalent in power to:
a) Pushdown automata
b) Finite automata (DFA/NFA)
33. • The union of two regular languages L and M is represented as:
a) LM
b) L + M (or L U M)
34. • Regular languages are closed under:
a) Only union
b) Union, intersection, complementation, concatenation, and Kleene star
35. • The pumping lemma is used to:
a) Prove a language is regular
b) Prove a language is not regular
36. • According to the pumping lemma, for any sufficiently long string w in a regular
language:
a) w can be split into parts xyz with y possibly empty
b) w can be split into xyz with y not empty and |xy| ≤ N
37. • Two finite automata are equivalent if:
a) They have the same number of states
b) They accept exactly the same set of strings
38. • The construction for the intersection of two DFAs results in:
a) A DFA with state set equal to the union of the two state sets
b) A DFA with state set equal to the Cartesian product of the two state sets
39. • Regular expressions in Kleene star (R*) denote:
a) Exactly one repetition of R
b) Zero or more repetitions of R
40. • The order of precedence for regular expression operators from highest to lowest is:
a) + (union), * (Kleene star), concatenation
b) * (Kleene star), concatenation, + (union)
41. • A Context-Sensitive Grammar (CSG) has productions of the form:
a) A → ε
b) α1 A α2 → α1 β α2 (where |β| ≥ |A|)
42. • The language generated by the CSG with rules S → aAbc, Ab → bA, etc., is:
a) {anbn | n ≥ 1}
b) {anbncn | n ≥ 1}
43. • The relation between CFGs and PDAs is that:
a) CFGs are more powerful than PDAs
b) Every CFL can be accepted by some PDA
44. • A Pushdown Automaton (PDA) is basically an ε-NFA plus:
a) Multiple tapes
b) A stack
45. • The transition function δ of a PDA takes as input:
a) (current state, input symbol) only
b) (current state, input symbol, top stack symbol)
46. • A PDA accepts a language by:
a) Always empty stack only
b) Either by final state or empty stack
47. • The instantaneous description (ID) of a PDA is:
a) (current input, current state)
b) (current state, unread input, current stack contents)
48. • In the PDA for language {anbn | n≥1}, the stack is used to:
a) Push input symbols directly
b) Store the count of 'a's to match with 'b's
49. • A PDA that accepts by empty stack:
a) Needs a designated final state
b) Does not require a designated final state
 50. • The PDA that accepts the language LwwR has states:
a) {q0, q1}
b) {q0, q1, q2}
51. • In PDA transitions, if Y=ε, it means:
a) Push Y on the stack
b) Pop the stack top
52. • PDA configurations are denoted as (q, w, y), where y is:
a) The input string
b) The current stack contents
53. • For every PDA accepting by empty stack, there exists an equivalent PDA accepting
by final state. True or False?
a) False
b) True
54. • The language of balanced parentheses can be accepted by a PDA.
a) No, because it is not context-free
b) Yes, because it is context-free
55. • PDA is used in compiler design mainly for:
a) Memory management
b) Syntax analysis (parsing)
56. • In a PDA, the stack top replacement string Y is pushed in:
a) Left to right order
b) Reverse order
57. • The language {wwR | w ∈ {0,1}*} is accepted by:
a) DFA
b) PDA
58. • Non-determinism in PDA means:
a) The PDA has only one possible next move
b) The PDA may have multiple possible next moves
59. • The initial stack symbol in a PDA is typically:
a) ε (empty)
b) A designated symbol like Z0
60. • To simulate acceptance by empty stack in a PDA that accepts by final state, a new
symbol X0 is:
a) Popped at the start
b) Pushed at the start

1. Finite Automata (DFA, NFA, ε-NFA)

# Question A B C D Ans.
A DFA accepts a string
w iff the state reached the start- a dead- the accept-state any non-dead
1 C
after reading w belongs state set state set set state
to ___.
Which of the following ε-moves L(N)L(N)L(N) is
There exists L(N)L(N)L(N)
2 is false for every NFA can be a regular C
an is always finite.
N? removed. language.
# Question A B C D Ans.
equivalent
DFA.
When converting an ε-
NFA to an equivalent
the lone the new the full power
3 DFA, the ε-closure of all accept states B
dead state start state set of states
the start state(s)
becomes ___.
In the subset-
construction algorithm,
4 how many DFA states nnn 2n2n2n n2n^2n2 2n2^{n}2n D
may be created for an
NFA with n states?
A transition labelled
write 0, read read 0,
5 0/1 in a Mealy machine write 1, read 0 flip the bit B
1 output 1
means ___.

2. Regular Expressions & Regular Languages

Questio An
# A B C D
n s.
The
languag
e of the
RE only equal #0s and all strings of
1 no substring 00 no substring 11 B
(01*)|10 #1s length 2
*
contains
___.
Which
algebrai
c law is
(E+F)+G=E+(F+G)(E (E\*)\*=E\*(E
invalid
E+F=F+EE+F = +F)+G = EF=FEEF = ^\*)^\* =
2 for all C
F+EE+F=F+E E+(F+G)(E+F)+G=E FEEF=FE E^\*(E\*)\*=E\
regular
+(F+G) *
expressi
ons E,
F?
The *
operator
on a
non- a language the empty
3 a finite language an infinite language C
empty with ε language
regular
languag
e always
 Questio An
# A B C D
n s.
yields
___.
Arden’s
theorem
solves
equation
s of the
form
4 R=Q+R QQQ has no ε PPP has no ε PPP contains ε RRR is finite B
PR = Q
+
RPR=Q
+RP
provided
___.
The RE
that
denotes
“all
(0+1)\*01(0+1)^\*01( 01(0+1)\*01(0+1)^\*0 0\*1\*0^\*1^\* (01)\+(01)^\+(
5 binary A
0+1)\*01 1(0+1)\* 0\*1\* 01)\+
strings
ending
in 01” is
___.

3. Pumping Lemma & Closure Properties

# Question A B C D Ans.
the length
In the pumping lemma for
the alphabet the the #states of of the
1 regular languages, N (the C
size #transitions some DFA shortest
pumping length) equals ___.
string
Regular languages are not infinite
2 complement reversal homomorphism D
closed under ___. intersection
To show language
applies applies the
L={0n1n∣n≥0}L=\{0^n1^n\mid constructs a builds a
3 Arden’s pumping C
n\ge0\}L={0n1n∣n≥0} is non- DFA regex
theorem lemma
regular, one typically ___.

4. Context-Free Grammar (CFG)

 Ans
# Question A B C D
.
the
A parse-tree’s
the yield rightmos
leaves, read the sequence of
1 the leftmost derivation (derived t B
left-to-right, variables
string) derivatio
form ___.
n
Which
grammar type
allows
productions
2 A→aBA \to Type-0 Type-1 Type-2 Type-3 C
aBA→aB and
A→εA \to
\varepsilonA→
ε?
A CFG is
2 leftmost
ambiguous if terminals
3 no derivation derivation infinite length B
some string has only
s
___.
Chomsky A→BCA\to
Normal Form BCA→BC or A→aBA\t exactly
A→εA\to\varepsilonA
4 requires every A→aA\to aA→a or o two A
→ε only
production to S→εS\to\varepsilonS aBA→aB terminals
be ___. →ε
Greibach
Normal Form
ensures the two
5 a non-terminal a terminal ε B
RHS of each terminals
rule begins with
___.

5. Pushdown Automata (PDA) & Context-Free Languages

# Question A B C D Ans.
A PDA differs from an
1 a queue a stack two tapes ε-moves B
NFA by having ___.
A PDA that accepts by
same as
2 empty stack needs how none required exactly one at least one A
#rules
many accepting states?
The language
{anbn∣n≥1}\{a^nb^n\mid
stores input counts matching stores reverses
3 n\ge1\}{anbn∣n≥1} is B
symbols a’s states the string
accepted by a PDA
because the stack ___.
# Question A B C D Ans.
Deterministic PDA
(DPDA) are strictly less
balanced regular
4 powerful than general 0n1n0^n1^n0n1n wwRww^RwwR B
parentheses languages
PDA because they cannot
recognise ___.
Compiler syntax analysis
a Turing a regex
5 most closely corresponds a DFA a PDA B
machine engine
to designing ___.

6. Turing Machines & Undecidability

Ans
# Question A B C D
.
always halts on
uses only
A Turing-recognisable language halts and accepts,
1 never halts finite B
is one for which a TM ___. answers may loop
memory
yes/no on rejects
The Halting Problem
semi-
2 HALTTMHALT_{TM}HALTT decidable regular context-free B
decidable
M is ___.
A TM with k two-way infinite polynomia
exponential no impossibilit
3 tapes can be simulated by a l C
slowdown slowdown y
standard single-tape TM with ___. slowdown
it is
both it and
A language is recursively its recognised it can be
its
4 enumerable but not recursive if complemen but not decided by a C
complemen
___. t is regular decided by PDA
t are RE
some TM
TMs
capture the every
The Church–Turing thesis states DPDAs =
5 intuitive NP = P language is B
that ___. PDAs
notion of decidable
algorithm

• multi correct

Which of the following problems are decidable?

a) Is it possible for a program to produce an output?
b) Is L′ (the complement of L), if L is context-free, also context-free?
c) Is L′ a regular language in the same way that L is?
d) Is L′ also recursive if L is a recursive language?

• Which of the following strings is in L* for L = {ab, aa, baa}?

a) abaabaaabaa
b) aaaabaaaa
c) baaaaabaaaab
d) baaaaabaa
• For lexical analysis of a modern language like Java, which machine model is required and sufficient?
a) Finite-state automata
b) Deterministic push-down automata
c) Non-deterministic push-down automata
d) Turing machine

• Which pair of automata has the greatest expressive power?

a) NFA and DFA
b) Non-deterministic PDA and Deterministic PDA
c) Deterministic vs. non-deterministic single-tape Turing machine
d) Single-tape vs. multi-tape Turing machine

• Which one of the following statements is FALSE?

a) Every regular language has its own minimal DFA.
b) Every NFA can be converted to a PDA of the same size.
c) Every context-free language’s complement is recursive.
d) Any non-deterministic PDA can be converted to an equivalent deterministic PDA.

• For the grammar S → aSa | bSb | a | b, the language generated over {a,b} is the set of
a) All palindromes
b) All palindromes of odd length
c) Strings with the same start and end symbol
d) All palindromes of even length

• The regular expression (0+1)*0(0+1)*0(0+1)* over {0,1} denotes

a) Strings containing the substring 00
b) Strings with at most two 0’s
c) Strings with at least two 0’s
d) Strings that start and end with the same symbol

• Let L₁ be recursive; L₂ and L₃ are recursively enumerable but not recursive. Which statement is unlikely to be
correct?
a) L₂ – L₁ is recursively enumerable.
b) L₁ – L₃ is recursively enumerable.
c) L₂ ∩ L₂ is recursively enumerable.
d) L₂ ∪ L₂ is recursively enumerable.

• For a binary string w of length n, let L be the set of all substrings of w. Minimum NFA states to accept L:
a) n – 1
b) n
c) n + 1
d) 2 n – 1

• For the languages

L₁ = {0^i 1^j | i ≠ j},
L₂ = {0^i 1^j | i = j},
L₃ = {0^i 1^j | i = 2j+1},
L₄ = {0^i 1^j | i ≠ 2j},
which is correct?
a) Only L₂ is context-free.
b) Only L₂ and L₃ are context-free.
c) Only L₁ and L₂ are context-free.
d) All are context-free.

• For S = (a + b*)* and T = (a + b)* over {a,b}, which relation holds?

a) S ⊂ T
b) T ⊂ S
c) S = T
d) S ∩ T = ∅

• Let grammar S → 0S0 | 00 generate language L. Which statement is correct?

a) L = ∅
b) L is regular but not empty
c) L is context-free but not regular
d) L is not context-free

• Which statement about context-free languages is true?

a) A DPDA can always accept any CFL.
b) The union of two CFLs is a CFL.
c) The intersection of two CFLs is a CFL.
d) The complement of a CFL is a CFL.

• The maximum states in a minimized DFA equivalent to an N-state NFA is at most

a) N²
b) 2^N
c) 2 N
d) N!

• Which of the following languages is regular?

a) { w x wᴿ | w,x ∈ (a+b)+ }
b) { w x wᴿ | w ∈ (a+b)*, x ∈ {a,b} }
c) { w wᴿ x | w,x ∈ (a+b)+ }
d) { w wᴿ | w ∈ (a+b)* }

• Over {a,b}*, let w be length n; L is strings ending with at least n a’s. Minimum NFA states:
a) n + 3
b) n + 1
c) n
d) 2^n

• Minimum DFA states for strings over {a,b} that start with b a a and end with a:
a) 10
b) 9
c) 8
d) 6

• With X,Y context-sensitive and R regular, which are true?

a) X ∪ R is regular.
b) X ∩ Y is context-sensitive.
c) The complement of Y is context-sensitive.
d) None of the above

• If X is decidable and Y undecidable, which must be true?

a) If X ≤ Z then Z is decidable.
b) If Z ≤ Y then Z is undecidable.
c) If Y ≤ Z then Z is undecidable.
d) If Z ≤ Y̅ then Z is decidable.

• Regular expression for strings over {a,b} with no consecutive b’s:

a) (a* b a a*)(b + ε)
b) (a + b a)*(b + ε)
c) (a* b a a*)*(b + ε) + a*
d) (a* b a*)*(b + ε) + a*(b + ε)
• Let X = languages accepted by DPDA by final state, Y = by empty stack. Which is true?
a) X ⊂ Y
b) X = Y
c) X ⊃ Y (proper)
d) None

• For X = 0*(10*)*, Y = (0* + 1*)*, which is correct?

b) X = Y

• Language L of TMs that halt on all input and whose language equals an undecidable language’s complement:
L is
a) Decidable & RE
b) Decidable & recursive
c) Decidable & non-recursive
d) Undecidable & RE

• Minimum NFA states for L = { (a^p)* | p prime }:

a) 3
b) 5
c) 2
d) 4

• Propositions:
X – deciding if a grammar is regular is decidable.
Y – if P regular and Q not, then P·Q is non-regular.
Z – pumping lemma can prove a language regular.
Which is true?
a) only X
 FORMAL LANGUAGES AND AUTOMATA THEORY (MCQ)
1.
A Language for which no DFA exist is a________
a) Regular Language
b) Non-Regular Language
c) May be Regular
d) Cannot be said
2.
A DFA cannot be represented in the following format
a) Transition graph
b) Transition Table
c) C code
d) None of the mentioned
3.
What the following DFA accepts?

a) x is a string such that it ends with ‘101’

b) x is a string such that it ends with ‘01’
c) x is a string such that it has odd 1’s and even 0’s
d) x is a strings such that it has starting and ending character as 1
4.
Which of the following will the given DFA won’t accept?

a) ε
b) 11010
c) 10001010
d) String of letter count 11
5.
Can a DFA recognize a palindrome number?
a) Yes
b) No
c) Yes, with input alphabet as ∑*
d) Can’t be determined
6.
Given:
L= {0n1n for n>=1}; Can there be a DFA possible for the language?
a) Yes
b) No
7.
Which among the following states would be notated as the final state/acceptance state?
L= {xϵ∑= {a, b} | length of x is 2}
a) q1
b) q2
c) q1, q2
d) q3
8
Given:
L= {wwR|wϵ{0,1} }Can there be a DFA possible for the language?
a) Yes
b) No

9.

Which among the following states would be notated as the final state/acceptance state?
L= {xϵ∑= {a, b} | length of x is atmost 2}
a) q1
b) q2
c) q0,q1, q2
d) q1, q2,q3
10.
How many languages are over the alphabet R?
a) countably infinite
b) countably finite
c) uncountable finite
d) uncountable infinite

ANSWERS

1.b
2.c
3.a
4.a
5.b
6.b
7.b
8.b
9.c
10.d

11.
State true or false:
Statement: Both NFA and e-NFA recognize exactly the same languages.
a) true
b) false
12.
Which of the following belongs to the epsilon closure set of a?

a) {f1, f2, f3}

b) {a, f1, f2, f3}
c) {f1, f2}
d) none of the mentioned
13.
The number of elements present in the e-closure(f2) in the given diagram:

a) 0
b) 1
c) 2
d) 3
14.
Is the language preserved in all the steps while eliminating epsilon transitions from a
NFA?
a) yes
b) no
15.
Remove all the epsilon transitions in the given diagram and compute the number of a-
transitions in the result?

a) 5
b) 7
c) 9
d) 6
16.
What does the following figure most correctly represents?

a) Final state with loop x

b) Transitional state with loop x
c) Initial state as well as final state with loop x
d) Insufficient Data
17.
Which of the following will not be accepted by the following DFA?

a) ababaabaa
b) abbbaa
c) abbbaabb
d) abbaabbaa
18.
The entity which generate Language is termed as:
a) Automata
b) Tokens
c) Grammar
d) Data
19.
Given grammar G:
(1)S->AS
(2)S->AAS
(3)A->SA
(4)A->aa
Which of the following productions denies the format of Chomsky Normal Form?
a) 2,4
b) 1,3
c) 1, 2, 3, 4
d) 2, 3, 4
20.
Suppose A->xBz and B->y, then the simplified grammar would be:
a) A->xyz
b) A->xBz|xyz
c) A->xBz|B|y
d) none of the mentioned
 ANSWERS

11.a
12.b
13.c
14.a
15.b
16.c
17.a
18.c
19.a
20.a
21.
Given Grammar: S->A, A->aA, A->e, B->bA
Which among the following productions are Useless productions?
a) S->A
b) A->aA
c) A->e
d) B->bA
22.
S->…->xAy->…->w, then A is _____
a) Reachable
b) Generating
c) Both Reachable and Generating
d) None of above
23.
For the given grammar G:
S->ABaC
A->BC
B->b| e
C->D| e
D-> d
Remove the e productions and generate the number of productions from S in the
modified or simplified grammar.
a) 6
b) 7
c) 5
d) 8
24.
Consider G=({S,A,B,E}, {a,b,c},P,S), where P consists of S →AB, A →a, B →b and E
→c.
Number of productions in P’ after removal of useless symbols:
a) 4
b) 3
c) 2
d) 5
25.
Given grammar G:
S->aS| AB
A-> e
B-> e
D-> b
Reduce the grammar, removing all the e productions:
a) S->aS| AB| A| B, D-> b
b) S->aS| AB| A| B| a, D-> b
c) S->aS| AB| A| B
d) None of the mentioned
26.
The format: A->aB refers to which of the following?
a) Chomsky Normal Form
b) Greibach Normal Form
c) Backus Naur Form
d) None of the mentioned
27.
NFA, in its name has ’non-deterministic’ because of :
a) The result is undetermined
b) The choice of path is non-deterministic
c) The state to be transited next is non-deterministic
d) All of the mentioned
28.
Given Language L= {xϵ {a, b}*|x contains aba as its substring}
Find the difference of transitions made in constructing a DFA and an equivalent NFA?
a) 2
b) 3
c) 4
d) Cannot be determined.
29.
The number of tuples in an extended Non Deterministic Finite Automaton:
a) 5
b) 6
c) 7
d) 4
30.
What is the relation between DFA and NFA on the basis of computational power?
a) DFA > NFA
b) NFA > DFA
c) Equal
d) Can’t be said
ANSWERS

21.d
22.c
23.d
24.a
25.b
26.b
27.b
28.a
29.a
30.c

31.
Which of the following is not an example of finite state machine system?
a) Control Mechanism of an elevator
b) Combinational Locks
c) Traffic Lights
d) Digital Watches
32.
Which of the following is the corresponding Language to the given DFA?

a) L= {x ϵ {0, 1} * | x ends in 1 and does not contain substring 01}

b) L= {x ϵ {0,1} * |x ends in 1 and does not contain substring 00}
c) L= {x ϵ {0,1} |x ends in 1 and does not contain substring 00}
d) L= {x ϵ {0,1} * |x ends in 1 and does not contain substring 11}
33.
Subset Construction method refers to:
a) Conversion of NFA to DFA
b) DFA minimization
c) Eliminating Null references
d) ε-NFA to NFA
34.
We can represent one language in more one FSMs, true or false?
a) TRUE
b) FALSE
c) May be true
d) Cannot be said
35.
The production of form non-terminal -> ε is called:
a) Sigma Production
b) Null Production
c) Unit Production
d) All of the mentioned
36.
Which of the following is an application of Finite Automaton?
a) Compiler Design
b) Grammar Parsers
c) Text Search
d) All of the mentioned
37.
Can a DFA recognize a palindrome number?
a) Yes
b) No
c) Yes, with input alphabet as ∑*
d) Can’t be determined
38.
Which of the following is not an example of finite state machine system?
a) Control Mechanism of an elevator
b) Combinational Locks
c) Traffic Lights
d) Digital Watches
39.
An NFA can be modified to allow transition without input alphabets, along with one or
more transitions on input symbols.
a) True
b) False
40.
The Grammar can be defined as: G=(V, ∑, p, S)
In the given definition, what does S represents?
a) Accepting State
b) Starting Variable
c) Sensitive Grammar
d) None of these
ANSWERS

31.d
32.b
33.a
34.a
35.b
36.d
37.b
38.d
39.a
40.b
41.
Which among the following cannot be accepted by a regular grammar?
a) L is a set of numbers divisible by 2
b) L is a set of binary complement
c) L is a set of string with odd number of 0
d) L is a set of 0n1n
42.
Which of the expression is appropriate?
For production p: a->b where a∈V and b∈_______
a) V
b) S
c) (V+∑)*
d) V+ ∑
43.
For S->0S1|∈ for ∑={0,1}*, which of the following is wrong for the language produced?
a) Non regular language
b) 0n1n | n>=0
c) 0n1n | n>=1
d) None of the mentioned
44.
The minimum number of productions required to produce a language consisting of
palindrome strings over ∑={a,b} is
a) 3
b) 7
c) 5
d) 6
45.
Which of the following statement is correct?
a) All Regular grammar are context free but not vice versa
b) All context free grammar are regular grammar but not vice versa
c) Regular grammar and context free grammar are the same entity
d) None of the mentioned
46.
Are ambiguous grammar context free?
a) Yes
b) No
47.
A->aA| a| b
The number of steps to form aab:
a) 2
b) 3
c) 4
d) 5
48.
The language accepted by Push down Automaton:
a) Recursive Language
b) Context free language
c) Linearly Bounded language
d) All of the mentioned
49.
Which of the following the given language belongs to?
L={ambmcm| m>=1}
a) Context free language
b) Regular language
c) Both (a) and (b)
d) None of the mentioned
50.
The most suitable data structure used to represent the derivations in compiler:
a) Queue
b) Linked List
c) Tree
d) Hash Tables
ANSWERS

41.d
42.c
43.d
44.c
45.a
46.a
47.b
48.b
49.d
50.c
51.
The Kleene Star operation accepts the following strings over set A = {0,1} | where string
s contains even number of 0 and 1
a) 01,0011,010101,....
b) 0011,11001100,...
c) ε,0011,11001100,...
d) ε,0011,11001100,...
52.
Moore Machine is an application of:
a) Finite automata without input
b) Finite automata with output
c) Non- Finite automata with output
d) None of the mentioned
53.
For a give Moore Machine, Given Input=’101010’, thus the output would be of length:
a) |Input|+1
b) |Input|
c) |Input-1|
d) Cannot be predicted
54.
Which of the following is a correct statement?
a) Moore machine has no accepting states
b) Mealy machine has accepting states
c) We can convert Mealy to Moore but not vice versa
d) All of the mentioned
55.
A regular language over an alphabet ∑ is one that cannot be obtained from the basic
languages using the operation
a) Union
b) Concatenation
c) Kleene*
d) All of the mentioned
56.
The output alphabet can be represented as:
a) δ
b) ∆
c) ∑
d) None of the mentioned
57.
Mealy Machine is an application of:
a) Finite automata without input
b) Finite automata with output
c) Non- Finite automata with output
d) None of the mentioned
58.
Statement1:Nullstring is accepted in Moore Machine.
Statement 2: There are more than 5-Tuples in the definition of Moore Machine.

Choose the correct option:

a) Statement 1 is true and Statement 2 is true
b) Statement 1 is true while Statement 2 is false
c) Statement 1 is false while Statement 2 is true
d) Statement 1 and Statement 2, both are false

59.
Statement 1: A Finite automata can be represented graphically; Statement 2: The nodes
can be its states; Statement 3: The edges or arcs can be used for transitions
Which of the following make the correct combination?
a) Statement 1 is false but Statement 2 and 3 are correct
b) Statement 1 and 2 are correct while 3 is wrong
c) None of the mentioned statements are correct
d) All of the mentioned
60.
In Moore machine, output is produced over the change of:
a) transitions
b) states
c) Both
d) None of the mentioned
ANSWERS

51.c
52.b
53.a
54.a
55.d
56.b
57.b
58.a
59.d
60.b
61.
Which of the following is a correct statement?
a) Moore machine has no accepting states
b) Mealy machine has accepting states
c) We can convert Mealy to Moore but not vice versa
d) All of the mentioned
62.
In mealy machine, the O/P depends upon?
a) State
b) Previous State
c) State and Input
d) Only Input
63.
Mealy and Moore machine can be categorized as:
a) Inducers
b) Transducers
c) Turing Machines
d) Linearly Bounder Automata
64.
Which among the following is the root of the parse tree?
a) Production P
b) Terminal T
c) Variable V
d) Starting Variable S
65.
Which of the following does the given parse tree correspond to?

a) P->1100
b) P->0110
c) P->1100ε
d) P->0101
66.
A grammar with more than one parse tree is called:
a) Unambiguous
b) Ambiguous
c) Regular
d) None of the mentioned
67.
A symbol X is ________ if there exists : S-> aXb
a) reachable
b) generating
c) context free
d) none of the mentioned
68.
A symbol X is called to be useful if and only if its is:
a) generating
b) reachable
c) both generating and reachable
d) none of the mentioned
69.
Which of the following is false for a grammar G in Chomsky Normal Form:
a) G has no useless symbols
b) G has no unit productions
c) G has no epsilon productions
d) None of the mentioned
70.
To derive a string using the production rules of a given grammar, we use:
a) Scanning
b) Parsing
c) Derivation
d) All of the mentioned
ANSWERS

61.a
62.c
63.b
64.d
65.b
66.b
67.a
68.c
69.d
70.b
71.
The e-NFA recognizable languages are not closed under :
a) Union
b) Negation
c) Kleene Closure
d) None of the mentioned
72.
Which of the following are undecidable problems?
a) Determining whether two grammars generate the same language
b) Determining whether a grammar is ambiguous
c) Both (a) and (b)
d) None of the mentioned
73.
If a problem has an algorithm to answer it, we call it _________
a) decidable
b) solved
c) recognizable
d) none of the mentioned
74.
The ratio of number of input to the number of output in a mealy machine can be given
as:
a) 1
b) n: n+1
c) n+1: n
d) None of the mentioned
75.
Which of the given are correct?
a) Moore machine has 6-tuples
b) Mealy machine has 6-tuples
c) Both Mealy and Moore has 6-tuples
d) None of the mentioned
76.
The major difference between Mealy and Moore machine is about:
a) Output Variations
b) Input Variations
c) Both
d) None of the mentioned
77.
Which of the following does not belong to input alphabet if S={a, b}* for any language?
a) a
b) b
c) e
d) none of the mentioned
78.
Every grammar in Chomsky Normal Form is:
a) regular
b) context sensitive
c) context free
d) all of the mentioned
79.
Which of the production rule can be accepted by Chomsky grammar?
a) A->BC
b) A->a
c) S->e
d) All of the mentioned
80.
A push down automaton employs ________ data structure.
a) Queue
b) Linked List
c) Hash Table
d) Stack
ANSWER
71.d
72.c
73.a
74.a
75.c
76.a
77.c
78.c
79.d
80.d
81.
Push down automata accepts _________ languages.
a) Type 3
b) Type 2
c) Type 1
d) Type 0
82.
A string is accepted by a PDA when
a) Stack is empty
b) Acceptance state
c) Both (a) and (b)
d) None of the mentioned
83.
A context free grammar can be recognized by
a) Push down automata
b) 2 way linearly bounded automata
c) Both (a) and (b)
d) None of the mentioned
84.
The production of the form A->B , where A and B are non terminals is called
a) Null production
b) Unit production
c) Greibach Normal Form
d) Chomsky Normal Form
85.
In pushdown automata notation,what does the symbol z0 represents?
a) an element of G
b) initial stack symbol
c) top stack alphabet
d) all of the mentioned
86.
A turing machine operates over:
a) finite memory tape
b) infinite memory tape
c) depends on the algorithm
d) none of the mentioned
87.
Which of the functions are not performed by the turing machine after reading a symbol?
a) writes the symbol
b) moves the tape one cell left/right
c) proceeds with next instruction or halts
d) none of the mentioned
88.
Given Grammar G:
S->aA
A->a| A
B->B
The number of productions to be removed immediately as Unit productions:
a) 0
b) 1
c) 2
d) 3
89.
Given grammar:
S->aA
A->a
A->B
B-> A
B->bb
Which of the following is the production of B after simplification by removal of unit
productions?
a) A
b) bb
c) aA
d) A| bb
90.
CFGs can be parsed in polynomial time using__________
a) LR parser
b) CYK algorithm
c) SLR parser
d) None of the mentioned

ANSWERS

81.b
82.c
83.c
84.b
85.b
86.b
87.d
88.c
89.b
90.b
91.
The following move of a PDA is on the basis of:
a) Present state
b) Input Symbol
c) Both (a) and (b)
d) None of the mentioned
92.
Which among the following is not a part of the Context free grammar tuple?
a) End symbol
b) Start symbol
c) Variable
d) Production
93.
Which of the following automata takes stack as auxiliary storage?
a) Finite automata
b) Push down automata
c) Turing machine
d) All of the mentioned
94.
A null production can be referred to as:
a) String
b) Symbol
c) Word
d) All of the mentioned
95.
A push down automata can be represented as:
PDA= ε-NFA +[stack] State true or false:
a) true
b) false
96.
Which of the following does not have left recursions?
a) Chomsky Normal Form
b) Greibach Normal Form
c) Backus Naur Form
d) All of the mentioned
97.
Which of the following are correct statements?
a) TMs that always halt are known as Decidable problems
b) TMs that are guaranteed to halt only on acceptance are recursive ennumerable.
c) Both (a) and (b)
d) None of the mentioned
98.
With reference to binary strings, state true or false:
Statement: For any turing machine, the input alphabet is restricted to {0,1}.
a) true
b) false
99.
The decision problem is the function from string to ______________
a) char
b) int
c) boolean
d) none of the mentioned
100.
Which of the following is true for The Halting problem?
a) It is recursively ennumerable
b) It is undecidable
c) Both (a) and (b)
d) None of the mentioned
ANSWERS

91.c
92.a
93.b
94.a
95.a
96.b
97.c
98.a
99.c
100.c
 DEPARTMENT OF INFORMATION SCIENCE AND ENGINEERING

QUIZ Questions with Answers

Subject: Automata Theory and Compiler Design(AT & CD)-21CS51
1. Finite state machine is _______________ tuple machine.
a) 4
b) 5
c) 6
d) Unlimited
Answer: b

2. Number of states requires accepting string ends with 101.

a) 3
b) 4
c) 2
d) Can’t be represented.
Answer: b

3. Regular expression for all strings with and ends with ba is.
a) aba*b*ba
b) ab(ab)*ba
c) ab(a+b)*ba
d) All of the mentioned
Answer: c

4. Which of the following are the examples of finite state machine system?
a) Control Mechanism of an elevator, Traffic Lights
b) Combination Locks
c) Digital watches
d) Both a & b
Answer: d

5. Regular expressions are closed under P K

MAHESH
06.06.2024 10:47
a) Union Digitally Signed by
Principal
RIT office : 08172-243180 & 08172-243181
E-mail : isehod@rithassan.ac.in, web : www.rithassan.ac.in
 DEPARTMENT OF INFORMATION SCIENCE AND ENGINEERING

b) Intersection
c) Kleen star
d) All of the mentioned
Answer: d

6. Regular expression{0,1} is equivalent to

a) 0 U 1
b) 0/1
c) 0+1
d) All of the mentioned
Answer: d

7. Which of the following is a characteristic feature of a Pushdown Automaton (PDA)?

a) It can recognize context-free languages.
b) It can recognize regular languages.
c) It has an infinite number of states.
d) It can only perform deterministic operations.
Answer: a

8. What is a characteristic feature of a Turing Machine?

a) It can recognize context-sensitive languages.
b) It can only perform deterministic operations.
c) It has a finite number of states.
d) It can simulate any algorithmic process.
Answer: d

9. Which of the following statements best describes undecidability in the context of computational
theory?
a) Undecidability refers to the property of a problem that can be solved by a computer in finite
time.
b) Undecidability refers to the property of a problem that cannot be solved by a computer in any
finite amount of time. MAHESH PK
06.06.2024 10:47
Digitally Signed by
Principal
RIT office : 08172-243180 & 08172-243181
E-mail : isehod@rithassan.ac.in, web : www.rithassan.ac.in
 DEPARTMENT OF INFORMATION SCIENCE AND ENGINEERING

c) Undecidability refers to the property of a problem that can be solved by a computer with
unlimited resources.
d) Undecidability refers to the property of a problem that cannot be solved by any algorithm.
Answer: d

10. We have the language L={ab, aa, baa} the four strings given below : I) abaabaaabaa II)
aaaabaaaa III) baaaaabaaaab IV) baaaaabaa The Strings present in L*are
a) I , II and IV
b) I, II and III
c) II, III and IV
d) I, III and IV
Answer: a

11. Consider the grammar G,

S – AB
A – aa | ab| ba | bb
B – aBa | bBb | C
C – aa | ab | ba | bb
Which of the following string is generated by G?
a) bababbab
b) abaab
c) aaabbba
d) babaa
Answer: a, c

12. Subset Construction method refers to :

a) Conversion of NFA to DFA
b) DFA minimization
c) Eliminating Null references
d) ℇ- NFA to NFA
Answer: a
MAHESH P K
06.06.2024 10:47
Digitally Signed by
Principal
RIT office : 08172-243180 & 08172-243181
E-mail : isehod@rithassan.ac.in, web : www.rithassan.ac.in
 DEPARTMENT OF INFORMATION SCIENCE AND ENGINEERING

13. State true or false? Statement : An NFA can be modified to allow transition without input
alphabets, along with one or more transition on input symbols.
a) True
b) False
Answer: a

14. Which of the following statements best describes top-down parsing?

a) Top-down parsing starts from the root of the parse tree and works downwards to generate
the input string.
b) Top-down parsing starts from the leaves of the parse tree and works upwards to generate the
input string.
c) Top-down parsing involves shifting and reducing tokens to match the production rules of
the grammar.
d) Top-down parsing uses a stack data structure to store grammar rules and match them against
the input string.
Answer: A

15. What is a characteristic feature of LR parsing?

a) It is a top-down parsing technique.
b) It uses a stack to store intermediate states.
c) It can handle left-recursive grammars efficiently.
d) It builds a parse tree from left to right, performing rightmost derivation.
Answer: b

16. Which of the following statements best describes bottom-up parsing?

a) Bottom-up parsing starts from the root of the parse tree and works downwards to generate the
input string.
b) Bottom-up parsing starts from the leaves of the parse tree and works upwards to generate the
input string.
c) Bottom-up parsing involves shifting and reducing tokens to match the production rules of the
MAHESH P K
grammar. 06.06.2024 10:47
Digitally Signed by
Principal
RIT office : 08172-243180 & 08172-243181
E-mail : isehod@rithassan.ac.in, web : www.rithassan.ac.in
 DEPARTMENT OF INFORMATION SCIENCE AND ENGINEERING

d) Bottom-up parsing uses a stack data structure to store grammar rules and match them against
the input string.
Answer: c

17. What is the primary purpose of a syntax-directed definition (SDD)?

a) To specify the syntax of a programming language.
b) To specify the semantics of a programming language.
c) To define the structure of a parse tree.
d) To generate intermediate code during parsing.
Answer: b

18. Which of the following is an issue in the design of a code generator?

a) Optimizing compiler phases.
b) Lexical analysis techniques.
c) Register allocation strategies.
d) Error recovery mechanisms.
Answer: c

19. In Conversion of HLL to machine language the syntax analysis part is called as _____
a) Parsing
b) Lexical analysis
c) Semantic analysis
d) Linking
Answer: a

20. The errors that can be pointed out by the compiler are
a) Syntax errors
b) Sematic errors
c) Internal errors
d) Logical errors
Answer: a
MAHESH P K
06.06.2024 10:47
Digitally
21. One of the purposes of using Signed bycode in compilers is to:
intermediate
Principal
RIT office : 08172-243180 & 08172-243181
E-mail : isehod@rithassan.ac.in, web : www.rithassan.ac.in
 DEPARTMENT OF INFORMATION SCIENCE AND ENGINEERING

a) make parsing and semantic analysis simpler

b) improve error recovery and error reporting
c) increase the chances of reusing the machine independent code optimizer in other
compilers
d) improve the register allocation
Answer: c

22. Which of the following symbol table implementation is best suited if access time is to be
minimum ?
a) Linear list
b) Search tree
c) Hash Table
d) Self-organisation list
Answer: c

23. Match List-1 with List-ll according to input to the compiler phase that process it:

List I List II

A.
Syntax tree I. Code generator

Intermediate Semantic
B. II.
representation analyze
Lexical
C. Token stream III.
analyze

D. Character stream IV. Syntax analyze

Choose the correct answer from the options given below:

a) A-IV, B-III, C-I, D-II
b) A-II, B-I, C-IV, D-III
c) A-II, B-IV, C-I, D-III
d) A-IV, B-I, C-II, D-III MAHESH P K
06.06.2024 10:47
Answer: b Digitally Signed by
Principal
RIT office : 08172-243180 & 08172-243181
E-mail : isehod@rithassan.ac.in, web : www.rithassan.ac.in
 DEPARTMENT OF INFORMATION SCIENCE AND ENGINEERING

24. A set of instructions executed directly by a computer's central processing unit is ______
a) Command Language
b) Machine Language
c) Markup Language
d) Style Sheet Language
Answer: b

25. The number of tokens in the following C code segment is switch(inputvalue)

{
Case 1 : b = c*d; break;
Default : b = b++; break;
}
a) 27
b) 29
c) 26
d) 24
Answer: 26

26. Match the following:

Leftmost
(P) Lexical analysis (i)
derivation
(Q) Top down parsing (ii) Type checking
Regular
(R) Semantic analysis (iii)
expressions
Runtime Activation
(S) (iv)
environments records

a) P - i, Q – ii, R – iv, S – iii

b) P – iii, Q – i, R – ii, S – iv
MAHESH P K
c) P – ii, Q – iii, R – i, 06.06.2024
S – iv 10:47
Digitally Signed by
Principal
RIT office : 08172-243180 & 08172-243181
E-mail : isehod@rithassan.ac.in, web : www.rithassan.ac.in
 DEPARTMENT OF INFORMATION SCIENCE AND ENGINEERING

d) P – iv, Q – i, R – ii, S – iii

Answer: b

27. Consider the following statements

i. Symbol table is accessed only during lexical analysis and syntax analysis.
ii. Compilers for programming languages that support recursion necessarily need heap storage
for memory allocation in the run-time environment.
iii. Errors violating the condition any variable must be declared before its use are detected
during syntax analysis.
Which of the above statements is/are TRUE?
a) i only
b) i and iii only
c) ii only
d) None of i, ii, and iii
Answer: d

28. Consider the following grammar S- m | mn | mno

Choose correct statement from the following:
a) The grammar is LL (2)
b) The grammar is LL (4)
c) The grammar is LL (1)
d) The grammar is LL (3)
Answer: d

MAHESH P K
06.06.2024 10:47
Digitally Signed by
Principal
RIT office : 08172-243180 & 08172-243181
E-mail : isehod@rithassan.ac.in, web : www.rithassan.ac.in
6/5/24, 11:18 AM vmedulife Account

Rajeev Institute of Technology, Hassan

Stream : UG (Information Science and Engineering)

Title: QUIZ
Subject: Automata Theory and compiler Design (21CS51) - Theory | Faculty: Kannika Lakshmi D G
Academic Year: 2023-24 | Year: 3rd Year - 5th Semester | Negative Marking: Not Applicable
Marks: 20 | Date: 2024-03-14 | Duration: 120 minutes

Roll Seat Middle Score (Out of Percentage

Sr.No Number Number First Name Last Name Name 20) (%)

1 4RA21IS001 Abdul Faraz 19 95

2 4RA21IS002 Abhishek K 10 50

3 4RA21IS004 Anurag K R 17 85

4 4RA21IS005 Anusha K 19 95

5 4RA21IS006 Chandan R 19 95

6 4RA21IS009 Darshan B G 19 95

7 4RA21IS010 Darshan L Gowda 19 95

8 4RA21IS011 Devika Cm 19 95

9 4RA21IS012 Dhanush Ts 19 95

10 4RA21IS013 Dimpal K L 19 95

11 4RA21IS014 Dushyanth Hm 19 95

12 4RA21IS015 Gagan H 18 90

13 4RA21IS016 Guruprasad 20 100

14 4RA21IS017 Harshan H R Harshan 20 100

15 4RA21IS018 Inisha K 18 90

16 4RA21IS019 Istartha P D 15 75

17 4RA21IS020 Jeevitha 18 90

18 4RA21IS021 Kavana NS 19 95

19 4RA21IS022 Keerthana D Y 19 95

20 4RA21IS023 Likith BN 20 100

21 4RA21IS024 Manjunath S V 7 35

22 4RA21IS025 Mithun N 4 20

23 4RA21IS026 Mohammed Atha Atha 20 100

24 4RA21IS027 Nandini B S 20 100

MAHESH P K
25 4RA21IS028 06.06.2024 10:47
Nayan Kumar 20 100
Digitally Signed by
26 4RA21IS029 Principal
Nimra Javeed Not Solved

https://portal.vmedulife.com/faculty/exam/ManageExam.php?uid=NjY1MTk=&subId=ODUwOTU=&subName=QXV0b21hdGEgVGhlb3J5IGFuZC… 1/3
6/5/24, 11:18 AM vmedulife Account

Roll Seat Middle Score (Out of Percentage

Sr.No Number Number First Name Last Name Name 20) (%)

27 4RA21IS030 Nishchitha N 20 100

28 4RA21IS031 Sandeep PB 20 100

29 4RA21IS032 Pratibha C Y 20 100

30 4RA21IS033 Priyanka K M 20 100

31 4RA21IS034 Punith KJ 20 100

32 4RA21IS035 Rachana G C 19 95

33 4RA21IS036 Rakesh Gowda 20 100

34 4RA21IS037 Rithesh BR 19 95

35 4RA21IS038 Ruchin Anandan 20 100

36 4RA21IS039 Sanjana Br 20 100

37 4RA21IS040 Sanjana D D 18 90

38 4RA21IS041 Shambhavi BV 19 95

39 4RA21IS042 Sonu Nisar R N 20 100

40 4RA21IS043 Sonu Patel NL 20 100

41 4RA21IS044 Soorya Prakash S 20 100

42 4RA21IS045 Srujan SR 20 100

43 4RA21IS046 Sudarshan Mn 20 100

44 4RA21lS047 Sukumar K Suju 19 95

45 4RA21IS048 Swathi KS 20 100

46 4RA21IS049 Syed Sadath 18 90

47 4RA21IS050 Tanushree N 20 100

48 4RA21IS051 Tanzeela Banu 18 90

49 4RA21IS052 Thushara K 18 90

50 4RA21IS053 Ullas B V BV ULLAS B V 20 100

51 4RA21IS054 Varalakshmi D 18 90
R

52 4RA21IS055 Varun Kumar Ck 19 95

53 4RA21IS056 Vedalakshmi T 19 95
P

54 4RA21IS057 Vinay N V Vinay N V VINAY N V 19 95

55 4RA21IS058 Yadhav MD 20 100

56 4RA21IS059 Yashaswini R 20 100

57 4RA21IS060 Yashvanth HN 20 100

58 4RA21IS061 Yashwanth GOWDA B C 20 100

MAHESH P K
59 4RA21IS062
06.06.2024 10:47
Shashank R Shashank R SHASHANK R 18 90
Digitally Signed by
60 4RA21IS063 Principal
Kishore MP 20 100

https://portal.vmedulife.com/faculty/exam/ManageExam.php?uid=NjY1MTk=&subId=ODUwOTU=&subName=QXV0b21hdGEgVGhlb3J5IGFuZC… 2/3
6/5/24, 11:18 AM vmedulife Account

Roll Seat Middle Score (Out of Percentage

Sr.No Number Number First Name Last Name Name 20) (%)

61 4RA22IS400 Darshan Cp 16 80
Prakash

62 4RA22IS401 Gowthami Shetty S 12 60

63 4RA22IS402 Hitesh Kumar S 11 55

64 4RA22IS403 Kiran Mallappanahalli Manjunath 16 80

65 4RA22IS404 Sneha Cs 19 95

66 4RA22IS405 Vedashree DR 19 95

67 4RA22IS406 Vinay P 19 95

Analysis of QUIZ (2023-24) [Theory]

Name Marks Marks No. of No. of

Sr. of Theory / Obtained Obtained Student Student % of Student
No. Subject Practical Lowest Highest appeared pass % Pass Above 60%

1 Automata Theory 0 20 66 64 96.969696969697% 92.424242424242%

Theory
and
compiler
Design
(21CS51)

Signature of subject teacher (Kannika Lakshmi D G )

MAHESH P K
06.06.2024 10:47
Digitally Signed by
Principal

https://portal.vmedulife.com/faculty/exam/ManageExam.php?uid=NjY1MTk=&subId=ODUwOTU=&subName=QXV0b21hdGEgVGhlb3J5IGFuZC… 3/3