# Automata Theory Multiple Choice Question & Answers (MCQs) set-9

1. Which among the following is smallest for n=50

a) 2n2

b) n2+3n+7

c) n3

d) 2n

### View Answer

Answer: b

Explanation:

2n2=5000

n2+3n+7=2567

n3=125000

2n=1.13*1015

a) NFA

b) DFA

c) PDA

d) Can’t be said

### View Answer

Explanation: None.

a) |Input|+1

b) |Input|

c) |Input-1|

d) Cannot be predicted

### View Answer

Explanation: Initial state, from which the operations begin is also initialized with a value.

a) Op(t)= d(Op(t))

b) Op(t)= d(Op(t)i(t))

c) Op(t): ?

d) None of the mentioned

### View Answer

Explanation: The output of mealy machine depends on the present state as well as the input to that state.

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

Explanation: 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. If a string S is accepted by a finite state automaton, S=s1s2s3……sn where si?? and there exists a sequence of states r0, r1, r2…… rn such that d(r(i), si+1) =ri+1 for each 0, 1, …n-1, then r(n) is:

a) initial state

b) transition symbol

c) accepting state

d) intermediate state

### View Answer

Explanation: r(n) is the final state and accepts the string S after the string being traversed through r(i) other states where I ? 01,2…(n-2).

7. Predict the total number of final states after removing the e-moves from the given NFA?

a) 1

b) 2

c) 3

d) 0

### View Answer

Explanation: The NFA which would result after eliminating e-moves can be shown diagramatically.

A: {[p, q] | p ? A1, q does not belong to A2}

a) A1-A2

b) A2-A1

c) A1.A2

d) A1+A2

### View Answer

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.

a) NFA

b) DFA

c) NFA-l

d) All of the mentioned

### View Answer

Explanation: NFA-l or e-NFA is an extension of Non deterministic Finite Automata which are usually called NFA with epsilon moves or lambda transitions.

10. The automaton which allows transformation to a new state without consuming any input symbols:

a) NFA

b) DFA

c) NFA-l

d) All of the mentioned

### View Answer

Explanation: NFA-l or e-NFA is an extension of Non deterministic Finite Automata which are usually called NFA with epsilon moves or lambda transitions.

a) Type 0 language

b) Type 1 language

c) Type 2 language

d) Type 3 language

### View Answer

Explanation: It is a regular expression.

12. L is a regular Language if and only If the set of __________ classes of IL is finite.

a) Equivalence

b) Reflexive

c) Myhill

d) Nerode

### View Answer

Explanation: According to Myhill Nerode theorem, the corollary proves the given statement correct for equivalence classes.

a) Type 0

b) Type 1

c) Type 2

d) Type 3

### View Answer

Explanation: Type 3 refers to Regular Languages which is accepted by a finite automaton.

a) {w | w is a string of odd length}

b) {w | w is a string of length multiple of 3}

c) {w | w is a string of length 3}

d) All of the mentioned

### View Answer

Explanation: This regular expression can be used to eliminate the answers and get the result. The length can be even and as well more than 3 when R= (???) (???) (particular case).

a) Every language defined by any of the automata is also defined by a regular expression

b) Every language defined by a regular expression can be represented using a DFA

c) Every language defined by a regular expression can be represented using NFA with e moves

d) Regular expression is just another representation for any automata definition

### View Answer

Explanation: Using NFA with e moves, we can represent all the regular expressions as an automata. As regular expressions include e, we need to use e moves.