Multiple choice question for engineering
Set 1
1. 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
Answer
Answer: c [Reason:] We use this algorithm to simplify a finite automaton to regular expression or vice versa. We eliminate states while converting a given finite automata to its corresponding regular expression.
2. If we have more than one accepting states 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
Answer
Answer: d [Reason:] If there is more than one accepting state or if the single accepting state as an out degree , add a new accepting state, make all other states non accepting, and hold an e-transitions from each former accepting state to the new accepting state.
3. Which of the following is not a step in elimination of states procedure?
a) Unifying all the final states into one using e-transitions
b) Unify single transitions to multi transitions that contains union of input
c) Remove states until there is only starting and accepting states
d) Get the resulting regular expression by direct calculation
Answer
Answer: b [Reason:] While eliminating the states, we unify multiple transitions to one transition that contains union of input and not the vice versa.
4. Can the given state diagram be reduced?
a) Yes
b) No
Answer
Answer: a [Reason:] The state q2 can be eliminated with ease and the reduced state diagram can be represented as:
5. 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
Answer
Answer: a [Reason:] Brzozowski method takes a unique approach to generating regular expressions. We create a system of regular expressions with one regular expression unknown for each state in M, and then we solve the system for Rλ where Rλ is the regular expression associated with starting state qλ.
6. 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
Answer
Answer: a [Reason:] This method has the advantage over the transitive closure technique as it can easily be visualized.
7. The behaviour of NFA can be simulated using DFA.
a) always
b) never
c) sometimes
d) none of the mentioned
Answer
Answer: a [Reason:] For every NFA, there exists an equivalent DFA and vice versa.
8. 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
Answer
Answer: d [Reason:] For converting RE to DFA , first we convert RE to NFA (Thompson Construction), and then NFA is converted into DFA(Subset Construction).
9. State true or false:
Statement: For every removed state, there is a regular expression produced.
a) true
b) false
Answer
Answer: a [Reason:] For every state which is eliminated, a new regular expression is produced. The newly generated regular expression act as an input for a state which is next to removed state.
10. Is it possible to obtain more than one regular expression from a given DFA using the state elimination method?
a) Yes
b) No
Answer
Answer: a [Reason:] Using different sequence of removal of state, we can have different possible solution of regular expressions. For n-state deterministic finite automata excluding starting and final states, n! Removal sequences are there. It is very tough to try all the possible removal sequences for smaller expressions.
Set 2
1. In mealy machine, the O/P depends upon?
a) State
b) Previous State
c) State and Input
d) Only Input
Answer
Answer: c [Reason:] Definition of Mealy Machine.
2. 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
Answer: c [Reason:] Finite Automaton with Output has a common definition for both the categories.
3. 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
Answer
Answer: b [Reason:] The input can be taken in form of a binary string and can be verified.
4. 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
Answer: b [Reason:] The output of mealy machine depends on the present state as well as the input to that state.
5.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
Answer: a [Reason:] The number of output here follows the transitions in place of states as in Moore machine.
6. Mealy and Moore machine can be categorized as:
a) Inducers
b) Transducers
c) Turing Machines
d) Linearly Bounder Automata
Answer
Answer: b [Reason:] They are collectively known as Transducers.
7. The major difference between Mealy and Moore machine is about:
a) Output Variations
b) Input Variations
c) Both
d) None of the mentioned
Answer
Answer: a [Reason:] Mealy and Moore machine vary over how the outputs depends on prior one (transitions) and on the latter one(states).
8. 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
Answer: a [Reason:] Being an input dependent and output capable FSM, Mealy machine reacts faster to inputs.
9. Which of the following does the given Mealy machine represents?
a) 9’s Complement
b) 2’s Complement
c) 1’s Complement
d) 10’s Complement
Answer
Answer: c [Reason:] Inputs can be taken and can be verified.
10. 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
Answer: d [Reason:] It does not produce a language or a grammar or can be converted to a NFA.
Set 3
1. 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
Answer
Answer: c [Reason:] The automaton may be allowed to change its state without reading the input symbol using epsilon but this does not mean that epsilon has become an input symbol. On the contrary, one assumes that the symbol epsilon does not belong to any alphabet.
2. The number of final states we need as per the given language?
Language L: {an| n is even or divisible by 3}
a) 1
b) 2
c) 3
d) 4
Answer
Answer: b [Reason:]
3. An e-NFA is ___________ in representation.
a) Quadruple
b) Quintuple
c) Triple
d) None of the mentioned
Answer
Answer: b [Reason:] An e-NFA consist of 5 tuples: A=(Q, S, d, q0. F)
Note: e is never a member of S.
4. State true or false:
Statement: Both NFA and e-NFA recognize exactly the same languages.
a) true
b) false
Answer
Answer: a [Reason:] e-NFA do come up with a convenient feature but nothing new.They do not extend the class of languages that can be represented.
5. Design a NFA for the language:
L: {an| n is even or divisible by 3}
Which of the following methods can be used to simulate the same.
a) e-NFA
b) Power Construction Method
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: c [Reason:] It is more convenient to simulate a machine using e-NFA else the method of Power Construction is used from the union-closure of DFA’s.
6. 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
Answer
Answer: b [Reason:] The epsilon closure of the set q is the set that contains q, together with all the states which can be reached starting at q by following only epsilon transitions.
7. The number of elements present in the e-closure(f2) in the given diagram:
a) 0
b) 1
c) 2
d) 3
Answer
Answer: c [Reason:] The epsilon closure set of f2 consist of the elements:{f2, f3}. Thus the count of the element in the closure set is 2.
8. Which of the steps are non useful while eliminating the e-transitions for the given diagram?
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 e
d) None of the mentioned
Answer
Answer: d [Reason:] The given are the steps followed while eliminating epsilon transitions from a NFA or converting an e-NFA to just NFA.
9. Is the language preserved in all the steps while eliminating epsilon transitions from a NFA?
a) yes
b) no
Answer
Answer: a [Reason:] Yes, the language is preserved during the dteps of construction: L(N)=L(N1)=L(N2)=L(3).
10. 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
Answer
Answer: b [Reason:]
Set 4
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
Answer
Answer: b [Reason:] Finite automaton with an output is categorize din two parts: Moore M/C and Mealy M/C.
2. In Moore machine, output is produced over the change of:
a) transitions
b) states
c) Both
d) None of the mentioned
Answer
Answer: b [Reason:] Moore machine produces an output over the change of transition states while mealy machine does it so for transitions itself.
3. 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
Answer: a [Reason:] Initial state, from which the operations begin is also initialized with a value.
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
Answer
Answer: a [Reason:] Even ε, when passed as an input to Moore machine produces an output.
5. The total number of states and transitions required to form a moore machine that will produce residue mod 3.
a) 3 and 6
b) 3 and 5
c) 2 and 4
d) 2 and 5
Answer
Answer: a [Reason:]
6. Complete the given table according to the given Moore machine.
Present State
Next State
Output
0
1
Q0
Q1
Q2
1
Q1
Q2
1
Q2
Q0
a) Q0, Q2, 0
b) Q0, Q2, 1
c) Q1, Q2, 1
d) Q1, Q0, 0
Answer
Answer: a [Reason:] The table can be filled accordingly seeing the graph.
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
Answer
Answer: a [Reason:] The outputs are as per the input, produced.
8. The output alphabet can be represented as:
a) δ
b) ∆
c) ∑
d) None of the mentioned
Answer
Answer: b [Reason:] Source-The tuple definition of Moore and mealy machine comprises one new member i.e. output alphabet as these are finite machines with output.
9. 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
Answer: a [Reason:] Op(t)=δ(Op(t)) is the defined definition of how the output is received on giving a specific input to Moore machine.
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
Answer
Answer: a [Reason:] 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.
Set 5
1. Can a single tape turing machine be simulated using deterministic 2-stack turing machine?
a) Yes
b) No
c) Cannot be said
d) none of the mentioned
Answer
Answer: a [Reason:] The symbols to left of the head of turing macine being simulated can be stored on the stack while the symbols on the right of the head can be placed on another stack. On each stack, symbols closer to the TM’s head are placed closer to the top of the stack than symbols farther from the TM’s head.
2. A ___________ is a multi tape turing machine whose input tape is read only.
a) Counter Machine
b) Multi-stack
c) Alternating Turing machine
d) None of the mentioned
Answer
Answer: a [Reason:] Counter machines are offline(a multitape turing machine whose input is read only) whose storage tapes are semi-infinite and whose tape symbols contains only two symbols Z and a blank symbol B.
3. Instantaneous description of a counter machine can be described using:
a) the input tape contents
b) position of the input head
c) distance of storage heads from symbol Z
d) all of the mentioned
Answer
Answer: d [Reason:] Instantaneous description of a counter machine can be described by the state, the input tape contents, the position of input head, and the distance of storage heads from the symbol Z. The counter machine can really store a count on each tape and tell if the count is zero.
4. Which of the following parameters cannot be used to restrict a turing machine?
a) tape alphabets
b) number of tapes
c) number of states
d) none of these
Answer
Answer: d [Reason:] Another procedure to restrict a turing machine is to limit the size of tape alphabet or reduce the number of states. If the tape alphabets, number of tapes or number of states are limited, then there is only a finite number of different turing machine, so the restricted model is more powerful than the original one.
5. Linear Bounded Automaton is a:
a) Finite Automaton
b) Turing Machine
c) Push down Automaton
d) None of the mentioned
Answer
Answer: b [Reason:] Linear Bounded Automaton is a type of Turing Machine where tape is not allowed to move off the portion of the tape containing the input. It is a Turing machine with limited amount of memory.
6. State true or false:
Statement: Using a two track tape, we can use a semi infinite tape to simulate an infinte tape.
a) true
b) false
Answer
Answer: true [Reason:] A TM with a semi-infinite tape means that there are no cells to the left of the initial head position. A TM with a semi infinite tape simulates a TM with an infinite tape by using a two-track tape.
7. Which of the following is true with reference to semi-infinite tape using a two track tape?
a) Can simulate a two way tape
b) Upper track represents the head-right cells
c) Lower track represents the head-left cells
d) All of the mentioned
Answer
Answer: d [Reason:] The upper track represents the cells of the original TM that are at the right of the initial head position. The lower track represents the cells to the left of the initial head position, but in reverse order.
8. Which among the following options are correct?
Statement 1: TMs can accept languages that are not accepted by any PDA with one stack.
Statement 2: But PDA with two stacks can accept any language that a TM can accept.
a) Statement 1 and 2, both are correct
b) Statement 1 is correct but Statement 2 is false
c) Statement 2 is correct while Statement 1 is false
d) Statement 1 and 2, both are false
Answer
Answer: a [Reason:] Both the statements are true. Both the statements are properties of Multistack machines.
9. A two-way infinite tape turing machine is ________ superior than the basic model of the turing machine in terms of power.
a) more
b) less
c) no way
d) none of the mentioned
Answer
Answer: c [Reason:] A two way infinite tape turing machine is a turing machine with its input tape infinte in both directions, the other component being the same as the basic model.
10. For a basic turing machine, there exists an equivalent :
a) 2-counter machine
b) 3-counter machine
c) 4-counter machine
d) All of the mentioned
Answer
Answer: d [Reason:] For a basic TM, there exists a 2-counter, 3-counter and 4-counter machines
We can prove them using Deterministic two stack turing machine.
Counter machine:
