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 Tokens
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 require 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)*
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. A Turing machine is a _________ tuple finite automata
a. 5
b. 6
c. 7
d. 8
43. The read/write head of which finite automata is capable of moving in both directions?
a. DFA
b. NDFA
c. PDA
d. Turing machine
44. 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
45. A PDM behaves like an FSM when the number of auxiliary memory it has, is
a. 0
b. 1
c. 2
d. 4
46. 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
47. 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
48. 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
49. 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
50. Context free languages are closed under _____
a. Intersection or complementation
b. Union only
c. Union, concatenation and kleen star
d. Concatenation only
51. Context free languages are closed under
a. Union, kleen closure
b. Union, intersection
c. Intersection, complement
d. Complement only
52. Context free grammar are not closed under
a. Product
b. Complementation
c. Union
d. Kleen star
53. 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
54. 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
55. 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
56. 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
57. 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
58. 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
59. 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
60. 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
61. a* (a+b)* is equivalent to
a. a* + b*
b. (ab)*
c. a*b*
d. none of these
62. (0*1*)* is the same as
a. (0+1)*
b. (01)*
c. (10)*
d. None of these
63. 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
64. 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
65. 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)*
66. 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
67. 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
68. The logic of pumping lemma is a good example of
a. Recursion
b. Pigeon-hole principle
c. Iteration
d. Divide and conquer technique
69. 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
70. 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.
71. 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
72. Grammar that can be translated to DKA is a
a. Right linear grammar
b. Left linear grammar
c. Generic grammar
d. All of these
73. 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
74. 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)
75. 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)
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. A Turing machine is a _________ tuple finite automata
a. 5
b. 6
c. 7
d. 8
43. The read/write head of which finite automata is capable of moving in both directions?
a. DFA
b. NDFA
c. PDA
d. Turing machine
44. 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
45. A PDM behaves like an FSM when the number of auxiliary memory it has, is
a. 0
b. 1
c. 2
d. 4
46. 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
47. 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
48. 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
49. 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
50. Context free languages are closed under _____
a. Intersection or complementation
b. Union only
c. Union, concatenation and kleen star
d. Concatenation only
51. Context free languages are closed under
a. Union, kleen closure
b. Union, intersection
c. Intersection, complement
d. Complement only
52. Context free grammar are not closed under
a. Product
b. Complementation
c. Union
d. Kleen star
53. 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
54. 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
55. 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
56. 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
57. 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
58. 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
59. 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
60. 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
61. a* (a+b)* is equivalent to
a. a* + b*
b. (ab)*
c. a*b*
d. none of these
62. (0*1*)* is the same as
a. (0+1)*
b. (01)*
c. (10)*
d. None of these
63. 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
64. 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
65. 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)*
66. 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
67. 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
68. The logic of pumping lemma is a good example of
a. Recursion
b. Pigeon-hole principle
c. Iteration
d. Divide and conquer technique
69. 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
70. 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.
71. 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
72. Grammar that can be translated to DKA is a
a. Right linear grammar
b. Left linear grammar
c. Generic grammar
d. All of these
73. 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
74. 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)
75. 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)
0 Comments
if you have any doubts plz let me know...