1. Which of the following is a not a part of 5-tuple finite automata?
a. Initial state
b. Output Alphabet
c. Transition function
d. Input alphabets
Correct Answer: b
2. A language for which no DFA exist is a _________
a. Non-Regular Language
b. Regular Language
c. Maybe Regular
d. Cannot be said
Correct Answer: a
3. When are 2 finite states equivalent?
a. Same number of states as well as transitions
b. Same number of transitions
c. same number of states
d. Both are final states
Correct Answer: a
4. We can represent one language in more one FSMs, true or false?
a. TRUE
b. FALSE
c. Maybe true
d. Can’t be said
Correct Answer: a
5. 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
Correct Answer: d
6. Can a DFA recognize a palindrome number ?
a. No
b. Yes
c. Yes, but with input alphabet as ∑*
d. Can’t be determined
Correct Answer: a
7. How many languages are over the alphabet R?
a. countably infinite
b. countably finite
c. uncountable finite
d. uncountable finite
Correct Answer: d
8. There are _______ tuples in finite state machine.
a. 4
b. 6
c. unlimited
d. 5
Correct Answer: d
9. The sum of minimum & maximum number of final states for a DFA n state is equal to:
a. n-1
b. n+2
c. n+1
d. n
Correct Answer: c
10. δˆ tells us the best:
a. Kleene operation is performed on the set
b. how the DFA S behaves on a word u
c. the state is the dumping state
d. the final state has been reached
Correct Answer: b
11. Language of finite automata is .
a. Type 2
b. Type 0
c. Type 1
d. Type 3
Correct Answer: d
12. The maximum transition which can be performed over a state in a DFA? ∑= {a, b, c}
a. 3
b. 4
c. 2
d. 1
Correct Answer: a
13. Finite automata requires minimum _______ number of stacks.
a. 0
b. 1
c. 2
d. None of the mentioned
Correct Answer: a
14. NFA, in its name has ’non-deterministic’ because of :
a. The choice of path is non-deterministic
b. The result is undetermined
c. The state to be transited next is non-deterministic
d. All of the mentioned
Correct Answer: a
15. What is the relation between DFA and NFA on the basis of computational power?
a. Equal
b. DFA>NFA
c. DFA<NFA
d. Can’t be said
Correct Answer: a
16. In NFA, this very state is like dead-end non final state:
a. ACCEPT
b. DISTINCT
c. START
d. REJECT
Correct Answer: d
17. When two or more strings combine to form a new string is called:
a. Reverse string
b. Length of string
c. Regular expression
d. Concatenation
Correct Answer: d
18. Empty transition is possible in NFA.
a. True
b. False
c. Maybe true
d. Can’t be determined
Correct Answer: a
19. If by reversing a string it remains same then its called:
a. Concatenation
b. Reverse of strings
c. Regular expression
d. Palindrome
Correct Answer: d
20. Which among the following is not notated as infinite language?
a. L={ab}*
b. Factorial
c. Palindrome
d. Reverse
Correct Answer: b
21. The number of tuples in an extended Non Deterministic Finite Automaton:
a. 5
b. 6
c. 7
d. 4
Correct Answer: a
22. A ___________ is a substitution such that h(a) contains a string for each a.
a. Inverse Homomorphisam
b. Homomorphisam
c. Closure
d. Interchange
Correct Answer: b
23. Subset Construction method refers to:
a. Eliminating Null referemces
b. NFA minimization
c. Conversion of NFA to DFA
d. DFA minimization
Correct Answer: c
24. L is a regular Language if and only If the set of __________ classes of IL is finite.
a. Myhill
b. Nerode
c. Equivalence
d. Reflexive
Correct Answer: c
25. Concatenation Operation refers to which of the following set operations:
a. Intersaction
b. Dot
c. Union
d. Kleeene
Correct Answer: b
26. Regular sets are closed under union,concatenation and kleene closure.
a. Depends on non-regular set
b. True
c. False
d. Depends on regular set
Correct Answer: b
27. Complement of a DFA can be obtained by
a. no trival method
b. make final as a starting state
c. making final states non-final and non-final to final.
d. making starting state as final state.
Correct Answer: c
28. If L1 and L2 are regular sets then intersection of these two will be
a. Recursive
b. Non-Regular
c. Non-Recursive
d. Regular
Correct Answer: d
29. The entity which generate Language is termed as:
a. Data
b. Grammer
c. Automata
d. Tokens
Correct Answer: b
30. The scanner outputs:
a. Intermediate code
b. Machine code
c. Stream of tokens
d. Image file
Correct Answer: c
31. Reverse of a DFA can be formed by
a. making final as starting state and starting state as final state
b. making final state as non-final
c. using PDA
d. None of the mentioned
Correct Answer: a
32. Which of the technique can be used to prove thata language is non regular?
a. Pumping Lemma
b. Ardens theorem
c. Ogden’s Lemma
d. None of the mentioned
Correct Answer: a
33. If L1 is regular L2 is unknown but L1-L2 is regular ,then L2 must be
a. Decidable
b. Regular
c. Empty set
d. CFG
Correct Answer: b
34. The finite automata accept the following languages:
a. Context Sensitive Languages
b. Non Regular Langugages
c. Regular Languages
d. Context Free Languages
Correct Answer: c
35. The phase of compilation which involves type checking is:
a. Parsing
b. Semantic Analyzer
c. Scanning
d. Syntax directed translation
Correct Answer: d
36. Complement of (a + b)* will be
a. phi
b. null
c. a
d. b
Correct Answer: a
37. 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
Correct Answer: a
38. Homomorphism of a regular set is _______
a. Universal set
b. Non regular set
c. Regular set
d. Null set
Correct Answer: c
39. If L is DFA-regular, L’ is
a. DFA-regular
b. Non-finite
c. Non regular
d. None
Correct Answer: a
40. Arden’s theorem is true for:
a. Null transitions
b. More than one initial states
c. One initial state
d. Non-null transitions
Correct Answer: d
41. Which kind of proof is used to prove the regularit of a language?
a. Proof by contradiction
b. Direct proof
c. Proof by induction
d. All
Correct Answer: a
42. Which of the following is not a notion of Context free grammars?
a. Recursive Inference
b. Derivations
c. Sentential form
d. All
Correct Answer: d
43. The language of balanced paranthesis is
a. None of the mentioned
b. may be regular
c. non regular
d. regular
Correct Answer: c
44. Which of the given are correct?
a. Moore machine has 6-touples
b. Mealy machine has 5-touples
c. Both Mealy and Moore has 6-touples
d. None of the mentioned
Correct Answer: a
45. A push down automaton employs ________ data structure.
a. Queue
b. Linked List
c. Stack
d. Hash Table
Correct Answer: c
46. In mealy machine, the O/P depends upon?
a. State
b. Previous State
c. Only Input
d. State and Input
Correct Answer: d
47. Which of the following can be used to prove a language is not context free?
a. Ardens theorem
b. Power Construction method
c. Pumping Lemma
d. Regular Closure
Correct Answer: d
48. Which of the following is an utility of state elimination phenomenon?
a. DFA to Regular Expression
b. DFA to NFA
c. NFA to DFA
d. All
Correct Answer: a
49. In which order are the children of any node ordered?
a. From the left
b. From the left
c. Arbitrarily
d. None
Correct Answer: a
50. Regular expression are
a. Type 1 language
b. Type 2 language
c. Type 3 language
d. Type 0 language
Correct Answer: d