1. Assume the 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
Answer: d
Explanation: A partially ordered relation refers to one which is Reflexive, Transitive and Antisymmetric.
2. The non- Kleene Star operation accepts the following string 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
Answer: b
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
Answer: d
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
Hint: Nodes and Edges are for trees and forests too.
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
Answer: d
Explanation: It is possible to represent a finite automaton graphically, with nodes for states, and arcs for transitions.
5. The minimum number of states required to recognize an octal number divisible by 3 are/is
a) 1
b) 3
c) 5
d) 7
Answer: b
6. Which of the following is a not a part of 5-tuple finite automata?
a) Input alphabet
b) Transition function
c) Initial State
d) Output Alphabet
Answer: d
Explanation: A FA can be represented as FA= (Q, ∑, δ, q0, F) where Q=Finite Set of States, ∑=Finite Input Alphabet, δ=Transition Function, q0=Initial State, F=Final/Acceptance State).
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
Answer: a
8. The number of elements in the set for the Language L={xϵ(∑r) *|length if x is at most 2} and ∑={0,1} is_________
a) 7
b) 6
c) 8
d) 5
Answer: a
Explanation: ∑r= {1,0} and a Kleene* operation would lead to the following set=COUNT{ε,0,1,00,11,01,10} =7.
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;
Answer: b
Explanation: δ(QX∑) = Q1 is the correct representation of change of state. Here, δ is called the Transition function.
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
Explanation: ∑* represents any combination of the given set while ∑x represents the set of combinations with length x where x ϵ I.
11. Which of the following not an example 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
Answer: b
Explanation: Bounded information refers to one whose output is limited and it cannot be said what were the recorded outputs previously until memorized.
12. A Language for which no DFA exist is a________
a) Regular Language
b) Non-Regular Language
c) May be Regular
d) Cannot be said
Answer: b
Explanation: A language for which there is no existence of a deterministic finite automata is always Non Regular and methods like Pumping Lemma can be used to prove the same.
13. A DFA cannot be represented in the following format
a) Transition graph
b) Transition Table
c) C code
d) None of the mentioned
Answer: d
Explanation: A DFA can be represented in the following formats: Transition Graph, Transition Table, Transition tree/forest/Any programming Language.
15. 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
Answer: c
Explanation: Two states are said to be equivalent if and only if they have same number of states as well as transitions.
19. Can a DFA recognize a palindrome number?
a) Yes
b) No
c) Yes, with input alphabet as ∑*
d) Can’t be determined
Answer: b
Explanation: Language to accept a palindrome number or string will be non-regular and thus, its DFA cannot be obtained. Though, PDA is possible.
20. 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
Answer: d
Explanation: Proper and sequential combination of events leads the machines to work in hand which includes The elevator, Combinational Locks, Traffic Lights, vending machine, etc. Other applications of Finite machine state system are Communication Protocol Design, Artificial Intelligence Research, A Turnstile, etc.
21. 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
Answer: a
22. 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
Answer: a
Explanation: Construct the DFA and NFA individually, and the attain the difference of states.
23. An automaton that presents output based on previous state or current input:
a) Acceptor
b) Classifier
c) Transducer
d) None of the mentioned.
Answer: c
Explanation: A transducer is an automaton that produces an output on the basis of what input has been given currently or previous state.
24. 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
Answer: c
Explanation: The maximum number of sets for DFA converted from NFA would be not greater than 2n.
25. 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
Answer: b
Explanation: Non deterministic or deterministic depends upon the definite path defined for the transition from one state to another or undefined(multiple paths).
26. 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
Explanation: DFA is a specific case of NFA.
27. 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.
Answer: a
Explanation: The individual Transition graphs can be made and the difference of transitions can be determined.
28. The construction time for DFA from an equivalent NFA (m number of node)is:
a) O(m2)
b) O(2m)
c) O(m)
d) O(log m)
Answer: b
Explanation: From the coded NFA-DFA conversion.
29. If n is the length of Input string and m is the number of nodes, the running time of DFA is x that of NFA.Find x?
a) 1/m2
b) 2m
c) 1/m
d) log m
Answer: a
Explanation: Running time of DFA: O(n) and Running time of NFA =O(m2n).
30. 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
Answer: c
Explanation: NFA, while computing strings, take parallel paths, make different copies of input and goes along different paths in order to search for the result. This creates the difference in processing speed of DFA and NFA.
31. 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
Answer: b
Explanation: Finite automaton with an output is categorize din two parts: Moore M/C and Mealy M/C.
32. In Moore machine, output is produced over the change of:
a) transitions
b) states
c) Both
d) None of the mentioned
Answer: b
Explanation: Moore machine produces an output over the change of transition states while mealy machine does it so for transitions itself.
33. 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
Answer: a
Explanation: Initial state, from which the operations begin is also initialized with a value.
34. 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
Answer: a
Explanation: Even ε, when passed as an input to Moore machine produces an output.
37. 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
Answer: a
Explanation: The outputs are as per the input, produced.
38. The output alphabet can be represented as:
a) δ
b) ∆
c) ∑
d) None of the mentioned
Answer: b
Explanation: Source-The tuple definition of Moore and mealy machine comprises one new member i.e. output alphabet as these are finite machines with output.
39. The O/P 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
Answer: a
Explanation: Op(t)=δ(Op(t)) is the defined definition of how the output is received on giving a specific input to Moore machine.
40. 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
Answer: a
Explanation: Statement a and b is correct while c is false. Finite machines with output have no accepting states and can be converted within each other.
41. In mealy machine, the O/P depends upon?
a) State
b) Previous State
c) State and Input
d) Only Input
Answer: c
Explanation: Definition of Mealy Machine.
42. 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
Answer: c
Explanation: Finite Automaton with Output has a common definition for both the categories.
44. The O/P 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
Answer: b
Explanation: The output of mealy machine depends on the present state as well as the input to that state.
45.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
Answer: a
Explanation: The number of output here follows the transitions in place of states as in Moore machine.
46. Mealy and Moore machine can be categorized as:
a) Inducers
b) Transducers
c) Turing Machines
d) Linearly Bounder Automata
Answer: b
Explanation: They are collectively known as Transducers.
47. The major difference between Mealy and Moore machine is about:
a) Output Variations
b) Input Variations
c) Both
d) None of the mentioned
Answer: a
Explanation: Mealy and Moore machine vary over how the outputs depends on prior one (transitions) and on the latter one(states).
48. 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
Answer: a
Explanation: Being an input dependent and output capable FSM, Mealy machine reacts faster to inputs.
50. Which one among 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
Answer: d
Explanation: It does not produce a language or a grammar or can be converted to a NFA
51. Under which of the following operation, NFA is not closed?
a) Negation
b) Kleene
c) Concatenation
d) None of the mentioned
Answer: d
Explanation: NFA is said to be closed under the following operations:
a) Union
b) Intersection
c) Concatenation
d) Kleene
e) Negation
52. It is less complex to prove the closure properties over regular languages using
a) NFA
b) DFA
c) PDA
d) Can’t be said
Answer: a
Explanation: We use the construction method to prove the validity of closure properties of regular languages. Thus, it can be observe, how tedious and complex is the construction of a DFA as compared to an NFA with respect to space.
53. Which of the following is an application of Finite Automaton?
a) Compiler Design
b) Grammar Parsers
c) Text Search
d) All of the mentioned
Answer: d
Explanation: There are many applications of finite automata, mainly in the field of Compiler Design and Parsers and Search Engines.
55.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
Answer: c
Explanation: Thompson Construction method is used to turn a regular expression in an NFA by fragmenting the given regular expression through the operations performed on the input alphabets.
56. 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
Answer: a
Explanation: Idle is the state when data in form of packets is send and returns if NAK is received else waits for the NAK to be received.
57. Which among the following is not an application of FSM?
a) Lexical Analyser
b) BOT
c) State charts
d) None of the mentioned
Answer: d
Explanation: Finite state automation is used in Lexical Analyser, Computer BOT (used in games), State charts, etc.
60. 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
Explanation: We need to make the number of a as fixed i.e. 2 and b can be 2 or more. Thus, using this condition a finite automata can be created using 1 states.
62. A binary string is divisible by 4 if and only if it ends with:
a) 100
b) 1000
c) 1100
d) 0011
Answer: a
Explanation: If the string is divisible by four, it surely ends with the substring ‘100’ while a binary string divisible by 2 would surely end with the substring ‘10’.
63. Let L be a language whose FA consist 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
Answer: a
Explanation: If L leads to FA1, then for Lc, the FA can be obtained by exchanging the final and non-final states.
64. If L1 and L2 are regular languages, which among the following is an exception?
a) L1 U L2
b) L1 – L2
c) L1 ∩ L2
d) All of the mentioned
Answer: d
Explanation: It the closure property of Regular language which lays down the following statement:
If L1, L2 are 2- regular languages, then L1 U L2, L1 ∩ L2, L1C, L1 – L2 are regular language.
65. 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
Answer: a
Explanation: When set operation ‘-‘ is performed between two sets, it points to those values of prior set which belongs to it but not to the latter set analogous to basic subtraction operation.
67. 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 is not
c) Statement 1 and 2, both are true
d) Statement 1 and 2, both are false
Answer: c
Explanation: While the machine runs on some input string, if it has the choice to split, it goes in all possible way and each one is different copy of the machine. The machine takes subsequent choice to split further giving rise to more copies of the machine getting each copy run parallel. If any one copy of the machine accepts the strings, then NFA accepts, otherwise it rejects.
68. 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 2k.
a) True
b) False
Answer: a
Explanation: If K is the number of states in NFA, the DFA simulating the same language would have states equal to or less than 2k.
69. 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
Answer: d
Explanation: All the optioned mentioned are the instruction formats of how to convert a NFA to a DFA.
70. 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
Answer: a
Explanation: The maximum number of states an equivalent DFA can comprise for its respective NFA with k states will be 2k.
0 Comments