MCQ Computer Science

# 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

Explanation:
2n2=5000
n2+3n+7=2567
n3=125000
2n=1.13*1015

2. It is less complex to prove the closure properties over regular languages using:
a) NFA
b) DFA
c) PDA
d) Can’t be said

Explanation: None.

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

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

4. The O/P of Mealy machine can be represented in the following format:
a) Op(t)= d(Op(t))
b) Op(t)= d(Op(t)i(t))
c) Op(t): ?
d) None of the mentioned

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

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

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

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

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

8. 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

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.

9. 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

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

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.

11. (a ^ 5b ^ 5)* is example of ________
a) Type 0 language
b) Type 1 language
c) Type 2 language
d) Type 3 language

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

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

13. A finite automaton accepts which type of language:
a) Type 0
b) Type 1
c) Type 2
d) Type 3

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

14. Let for ?= {0,1} R= (???) *, the language of R would be
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

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).

15. Which of the following statements is not true?
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