Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages
Filter by Categories
nmims post
Objective Type Set
Online MCQ Assignment
Question Solution
Solved Question
Uncategorized

# 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View Answer

Answer: b [Reason:] 3. An e-NFA is ___________ in representation.
a) Quadruple
b) Quintuple
c) Triple
d) None of the mentioned

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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

### View 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:  .woocommerce-message { background-color: #98C391 !important; }