# 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

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

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

4. Can the given state diagram be reduced?

a) Yes

b) No

### View Answer

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

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

7. The behaviour of NFA can be simulated using DFA.

a) always

b) never

c) sometimes

d) none of the mentioned

### View Answer

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

9. State true or false:

Statement: For every removed state, there is a regular expression produced.

a) true

b) false

### View Answer

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

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

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

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

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

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

6. Mealy and Moore machine can be categorized as:

a) Inducers

b) Transducers

c) Turing Machines

d) Linearly Bounder Automata

### View Answer

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

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

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

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

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

2. The number of final states we need as per the given language?

Language L: {a^{n}| n is even or divisible by 3}

a) 1

b) 2

c) 3

d) 4

### View Answer

3. An e-NFA is ___________ in representation.

a) Quadruple

b) Quintuple

c) Triple

d) None of the mentioned

### View Answer

4. State true or false:

Statement: Both NFA and e-NFA recognize exactly the same languages.

a) true

b) false

### View Answer

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

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

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

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

9. Is the language preserved in all the steps while eliminating epsilon transitions from a NFA?

a) yes

b) no

### View Answer

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

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

2. In Moore machine, output is produced over the change of:

a) transitions

b) states

c) Both

d) None of the mentioned

### View Answer

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

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

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

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

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

8. The output alphabet can be represented as:

a) δ

b) ∆

c) ∑

d) None of the mentioned

### View Answer

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

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

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

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

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

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

5. Linear Bounded Automaton is a:

a) Finite Automaton

b) Turing Machine

c) Push down Automaton

d) None of the mentioned

### View Answer

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

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

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

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

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