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

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

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

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

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

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

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

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

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

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

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

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

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

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

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