1. The final state of a finite automaton is shown using a ______________
a. Circle
b. Dashed circle
c. Double circle
d. Arrow head incident on a circle
2. A finite automaton where there exists exactly one transition from a state on an input symbol is called a/an
a. DFA
b. NDFA
c. Mealy machine
d. Moore Machine
3. Two finite states are equivalent if they
a. Have same number of states
b. Have same number of edges
c. Have same number of states and edges
d. Recognize same set of Token
4. There are _________ tuples in finite state machine.
a. 4
b. 5
c. 6
d. unlimited
5. FSM can recognize
a. Any grammar
b. Only regular grammar
c. Both (a) and (b)
d. Only CG
6. Finite automata requires minimum ________ number of stacks
a. 1
b. 0
c. 2
d. All of the above
7. A DFA simulate the behavior of an NDFA by _________the number of states.
a. Increasing
b. Decreasing
c. Increasing or decreasing
d. Reducing
8. If the output function of a finite automata depends only on the present state and is independent of the current input, the model is called a/an ___________
a. DFA
b. NDFA
c. Mealy machine
d. Moore machine
9. An automaton in which the output depends only on the states of the machine is called a ___________ machine.
a. Mealy
b. PDA
c. TM
d. Moore
10. A Moore machine is a ________ tuple.
a. 5
b. 6
c. 7
d. 8
11. For a Moore machine if the input string is of length n, the output string is of length—
a. n+1
b. n
c. n-1
d. 2n
12. Finite state machine can recognize
a. Only regular grammar
b. Only ambiguous CFG
c. Any grammar
d. Any unambiguous grammar
13. Finite state machine __________ recognize palindromes.
a. Can
b. Cannot
c. May
d. May not
14. The recognizing capability of NDFSM and DFSM
a. Must be same
b. May be different
c. Must be different
d. None of the above
15. Any given transition graph has an equivalent
a. DFSM
b. Finite Automata
c. CFL
d. All of the above
16. R + R= ___________ , R is Regular expression
a. ^
b. Φ
c. R
d. None of these
17. Which of the following identity for regular expressions is false?
a. ^+RR*=R*
b. (P+Q)*=(P*Q*)*
c. ΦR=Φ
d. Φ+R=Φ
18. The true regular expression is _______
a. (r*s*)* = (r + s)*
b. (r + s)*= r* + s*
c. r*s* = r* + s*
d. r(*) = r*
19. The regular expression (a+b) means
a. a or b
b. a and b
c. a followed by b
d. Any number of a’s and b’s
20. Regular expression for all strings starts with ab and ends with bba is
a. aba*b*bba
b. ab(ab)*bba
c. ab(a+b)*bba
d. a*b*(a+b)*
21. Which is the regular expression that describes the set of all strings of 0’s and 1’s beginning with 0 and ending with 1?
a. (0+1)
b. 0(0+1)*1
c. 0(0+1)1
d. (0+1)*
22. Let P and Q be two regular expressions over ∑. If does not contain ^, then the equation in R, R=Q+RP has a unique solution given by
a. R=QP*
b. R=QP+
c. Q=RP
d. R=^ + R*R
23. Which of the following regular expression is true?
a. r(*) = r*
b. (r*s*)* = (r + s)*
c. (r + s)*= r* + s*
d. r*s* = r* + s*
24. The set of all strings over the alphabet ∑ = { a, b} ( including Ɛ ) is denoted by
a. (a + b)*
b. a*b*
c. (a* + b* )
d. ab*
25. The set which is not countable if we have ∑= { a, b} is
a. Set of all language over ∑ accepted by turing machine
b. Set of all regular language over ∑
c. Set of all string over ∑
d. Set of all language over ∑
26. The class of languages recognized by a finite automaton are called ________
a. Context sensitive set
b. Phrase structural set
c. Regular set
d. Context free set
27. Every grammar in Chomsky Normal Form
a. Regular
b. Context sensitive
c. Context free
d. All the mentioned
28. Which type of grammar is called context-free grammar?
a. Type 0
b. Type 1
c. Type 2
d. Type 3
29. CFG is recognized by a
a. Turing machine
b. Push down automata
c. 2 way linear bound automata
d. None of the above
30. Push down machine represent
a. Type 0 grammar
b. Type 1 grammar
c. Type 2 grammar
d. Type 3 grammar
31. The language accepted by push down automata is
a. Type 2
b. Type 0
c. Type 1
d. Type 3
32. Which one of the following finite automata uses a stack?
a. DFA
b. NDFA
c. PDA
d. Turing machine
33. Which type of symbol contain in the stack of PDA
a. Variable
b. Terminal
c. Both a and b
d. Stack symbol
34. The transition a push down automata makes is additionally dependent upon the
a. Stack
b. Input tape
c. Terminals
d. Current state
35. The PDA does not stop on accepting state and the stack is not empty, the string is:
a. Rejected
b. Goes into loop forever
c. Accepted
d. Unknown state
36. Which of the following is the most general phase structured grammar
a. Regular
b. Context-sensitive
c. Context-free
d. All of the above
37. A grammar is said to be ambiguous if there is/are _____________ for the grammar
a. One derivation tree
b. More than one
c. No derivation tree
d. Ambiguity
38. A context-free grammar G is ambiguous if there is same string w belongs to L(G) that has two distinct___________
a. Graph only
b. Parse tree
c. Grammar
d. None of the above
39. The intersection of a CFL and regular language
a. Is always regular
b. Need not be regular
c. May be regular
d. (a) and (c)
40. The intersection of a CFL and regular language___________
a. Need not be regular
b. Need not be context-free
c. Is always regular
d. Is always CF
41. The concept of FSA is much used in this part of the compiler.
a. Lexical analysis
b. Parser
c. Code generation
d. Code optimization
42. The language L= {akbk | k>=1 } is
a. Type-3 grammar
b. Type-2 grammar
c. Type-1 grammar
d. Type-0 grammar
43. R1 and R2 are regular sets. Which of the following is not true?
a. R1 and R2 need not be regular
b. S* àR1 is regular
c. R1à R2 is regular
d. R1 is regular
44. A Turing machine is a _________ tuple finite automata
a. 5
b. 6
c. 7
d. 8
45. The read/write head of which finite automata is capable of moving in both directions?
a. DFA
b. NDFA
c. PDA
d. Turing machine
46. A string is said to be accepted by a PDA in terms of __________
a. Reaching the final state from the initial state
b. Get an empty stack
c. Both a and b
d. Reach the initial state
47. A PDM behaves like an FSM when the number of auxiliary memory it has, is
a. 0
b. 1
c. 2
d. 4
48. The Turing machine that can simulate the behavior of any arbitrary Turing machine is known as a/an
a. Universal Turing machine
b. Non-deterministic Turing Machine
c. Multitape Turing machine
d. Deterministic Turing Machine
49. When does a Turing Machine M not accept a string and is said to halt?
a. M enters the final state
b. M halts in a non-accepting state.
c. M halts in the final state
d. M does not have a initial state
50. The intersection of context-free language with regular language is a___
a. Context-free language
b. General language
c. Irregular language
d. None of the above
51. The intersection of context free language and a regular language is
a. Context-free
b. Regular but not context-free
c. Neither context-free nor regular
d. Both regular and context-free
52. Context free languages are closed under____________
a. Intersection or complementation
b. Union only
c. Union, concatenation and kleen star
d. Concatenation only
53. Context free languages are closed under
a. Union, kleen closure
b. Union, intersection
c. Intersection, complement
d. Complement only
54. Context free grammar are not closed under
a. Product
b. Complementation
c. Union
d. Kleen star
55. A grammar that produces more than one parse tree for same sentence is called
a. Unambiguous
b. Ambiguous
c. Regular
d. None of the above
56. If every string of a language can be determined, whether it is legal or illegal called
a. Undecidable
b. Decidable
c. Interpretive
d. Non-deterministic
57. A grammar is called context-sensitive or context-dependent if all its productions are ___________ productions
a. Type 1
b. Type 0
c. Type 2
d. Type 3
58. A _________ set is a set X for which we have a procedure to determine whether a given element belongs to X or not.
a. Recursively enumerable
b. Context free
c. PDA
d. TM
59. P,Q,R are languages, if P and R are regular and if PQ=R, then
a. Q has to be regular
b. Q need to be regular
c. Q cannot be regular
d. Q cannot be CFL
60. Which of the following is not possible algorithmically?
a. Regular grammar to context free grammar
b. Non-deterministic PDA to deterministic PDA
c. Non-deterministic FSA to deterministic FSA
d. None of the above
61. Pumping lemma is generally used for
a. Given grammar is regular
b. Given grammar is not regular
c. Whether two given regular expression are equivalent or not
d. All of the above
62. A ___________ in a context-free grammar G is a production of the form AàB, where A and B are variables in G.
a. Duplicate production
b. Unit production
c. Unique production
d. Null production
63. { anbn | n>=1 } is
a. Regular
b. Context free but not regular
c. Context sensitive but not context free
d. None of these
64. { anb2n | n>=1 } is accepted by a
a. Finite automaton
b. Non deterministic finite automaton
c. pda
d. None of these
65. { anbn | n>=1} is accepted by a pda:
a. By null store and also by final state
b. By null store but not by final state
c. By final state but not by null store
d. None of these
66. { a2n | n>=1 } is represented by the regular expression
a. (aa)*
b. a*
c. aa*a
d. a* a*
67. The regular grammar generating { an: n>=1} is
a. ( {s}, {a}, {sàas} , s)
b. ( {s}, {a}, {sàss, sàa })
c. ({s}, {a}, { sàas}, s)
d. ({s}, {a}, {sàas, sàa}s)
68. If G= ({S}, {a}, {SàSS}, S), what is the language generated by G?
a. L(G)=Φ
b. L(a)=0n1n
c. L(a)=S
d. L(a)=an
69. What is the type of the following production?
A à abA
a. Type 0
b. Type 1
c. Type 2
d. Type 3
70. A context free grammar is said to be in Chomsky Normal Form if every production is of the form ______________
a. Aàa, or A à BC
b. A àaB
c. A àBa, A àaB
d. A àaa
71. Any string of terminals that can be generated by the following CFG is
S à XY
X à aX | bX |a
Y à Ya | Yb |a
a. Has atleast one b
b. Should end in a
c. Has no consecutive a’s or b’s
d. Has atleast two a’s
72. The CFG Sà aS| bS | a | b is equivalent to regular expression
a. (a+b)
b. (a+b)(a+b)*
c. (a+b)(a+b)
d. (a* + b* )
73. S à ABCc | Abc
BA à AB
Bb à bb
Ab àab
Aa à aa
Which of the following sentence can be derived by this grammar?
a. abc
b. aab
c. abcc
d. abbb
74. Which one of the following is an unit production?
a. A àaB
b. Aàa
c. AàB
d. AàBa
75. A _____________ is a nondeterministic Turing machine which has a single tape whose length is not infinite but bounded by a linear function of the length of the input string.
a. Linear bounded automaton
b. Transformation Grammar
c. Generative Grammar
d. Context-sensitive language
76. If a grammar G has three productions
SàaSa/bSb/c, then
a. abcba and bacab € L(G)
b. abcba and abcab € L(G)
c. accca and bcccb € L(G)
d. acccb and bccca € L(G)
77. The highest type member which can be applied to the productions
SàAa, Aàc/Ba, Bàabc is
a. 2
b. 3
c. 1
d. 4
78. a* (a+b)* is equivalent to
a. a* + b*
b. (ab)*
c. a*b*
d. none of these
79. (0*1*)* is the same as
a. (0+1)*
b. (01)*
c. (10)
d. None of these
80. The regular expression 0*(10*) is similar to
a. 0 + ( 0 + 10)*
b. ( 0 + 1)* 10(1 + 0)*
c. (1*0)*1*
d. None of the above
81. What is the regular expression for the set { 12n+1/n>=0 } ?
a. (11)*
b. 1 (11)*
c. 1* (11)
d. (11)* 1*
82. The minimum number of states in any DFA accepting the regular language L=(111 + 1111 1)* is
a. 5
b. 7
c. 9
d. 11
83. The set of all strings over {a,b} of even length is represented by the regular expression
a. (ab+aa+bb+ba)*
b. (a+b)*(a*+b)*
c. (aa+bb)*
d. (ab+ba)*
84. ab* +b* represents all strings w over {a,b}
a. Starting with an a and having no other a’s or having no a’s but only b’s.
b. Starting with an a followed by b’s
c. Having no a’s but only b’s
d. None of these
85. The set of all strings over {a,b} having abab as a substring is represented by
a. a*ababb*
b. (a+b)* abab(a+b)*
c. a*b* ababa* b*
d. (a+b)* abab
86. The logic of pumping lemma is a good example of
a. Recursion
b. Pigeon-hole principle
c. Iteration
d. Divide and conquer technique
87. The concatenation of the labels of the leaves of a derivation tree without repetition in the left-to-right ordering is known as the ___________ of the derivation tree.
a. Length
b. Breadth
c. Label
d. Yield
88. What is the use of pumping lemma for context-free languages?
a. To prove that certain languages are not context-free
b. To prove that certain languages are context-free
c. To prove that certain languages are not regular
d. To prove that certain language are regular.
89. The automaton corresponding to an LR(K) grammar is
a. A deterministic finite automaton
b. A nondeterministic finite automaton
c. A deterministic PDA
d. A nondeterministic PDA
90. Grammar that can be translated to DKA is a
a. Right linear grammar
b. Left linear grammar
c. Generic grammar
d. All of these
91. According to Kleen’s theorem, the regular sets over ∑ is the smallest class R containing a for every a € ∑ and NOT closed under _____
a. Union
b. Concatenation
c. Intersection
d. Closure
92. A transition system accepts a string w in ∑* if
(A) there exists a path which originates from some initial state, goes along the arrows, and terminates at some final state.
(B) the path value obtained by concatenation of all edges-labels of the path is equal to w.
a. (A) only
b. (B) only
c. Both (A) and (B)
d. Neither (A) nor (B)
93. Which of the following statements are False?
(A) A set X is recursive if we have an algorithm to determine whether a given element belongs to X or not.
(B) A Context Sensitive language is recursive
a. (A) only
b. (B) only
c. Both (A) and (B)
d. Neither (A) nor (B)
94. Which of the following is/are true?
(i) L= { aP | P is a prime } is not regular
(ii) L= { ww | w € {a,b}* } is not regular
a. Both (i) and (ii)
b. Neither (i) nor (ii)
c. (i) is true but (ii) is false
d. (ii) is true but (i) is false
95. In bottom-up parsing, we build the derivation from _____ to _____.
a. Input string to S, S à start node
b. S to input string, S à start node
c. Both a & b
d. None of these
96. Which of the following CFG cannot be simulated by an FSM?
a. SàSa / b
b. SàaSb / ab
c. Sàabx, x-ey, y-d/ax
d. None of the above
97. The set { anbn|n=1,2,3……} can be generated by the CFG
a. Sà ab | aSb
b. SàaaSbb |ab |aabb
c. Sà aaSbb + abs
d. Sà ab | aSb |B
98. Which one of the following is true for the language { ambncm+n | m, n>=1 } ?
a. It is context free
b. It is regular
c. It is type-0
d. It is context sensitive
99. Consider the grammar___________
S àPQ | SQ | PS
Pàx
Q ày
To get a string of n terminals the number of productions are to be used in_____
a. n2
b. n+1
c. 2n
d. 2n-1