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

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

2. The non- Kleene Star operation accepts the following string of finite length over set A = {0,1} | where string s contains even number of 0 and 1
a) 01,0011,010101
b) 0011,11001100
c) e,0011,11001100
d) e,0011,11001100

Answer: b
Explanation: The Kleene star of A, denoted by A*, is the set of all strings obtained by concatenating zero or more strings from A.

3. A DFA cannot be represented in the following format
a) Transition graph
b) Transition Table
c) C code
d) None of the mentioned

4.Predict the following step in the given bunch of steps which accepts a strings which is of even length and has a prefix=’01’
d (q0, e) =q0 < d(q0,0) =d (d (q0, e),0) =d(q0,0) =q1 < _______________
a) d (q0, 011) =d (d (q0,1), 1) =d (q2, 1) =q3
b) d (q0, 01) =d (d (q0, 0), 1) = d (q1, 1) =q2
c) d (q0, 011) =d (d (q01, 1), 1) =d (q2, 0) =q3
d) d (q0, 0111) =d (d (q0, 011), 0) = d (q3, 1) =q2

5. d*(q,ya) is equivalent to .
a) d((q,y),a)
b) d(d*(q,y),a)
c) d(q,ya)
d) independent from d notation

6. Which of the following is correct proposition?
Statement 1: Non determinism is a generalization of Determinism.
Statement 2: Every DFA is automatically an NFA
a) Statement 1 is correct because Statement 2 is correct
b) Statement 2 is correct because Statement 2 is correct
c) Statement 2 is false and Statement 1 is false
d) Statement 1 is false because Statement 2 is false

7. We can represent one language in more one FSMs, true or false?
a) TRUE
b) FALSE
c) May be true
d) Cannot be said

8. Which of the following options is correct for the given statement?
Statement: If K is the number of states in NFA, the DFA simulating the same language would have states less than 2k.
a) True
b) False

9. Let N (Q, ?, d, q0, A) be the NFA recognizing a language L. Then for a DFA (Q’, ?, d’, q0’, A’), which among the following is true?
a) Q’ = P(Q)
b) ?’ = d’ (R, a) = {q ? Q | q ? d (r, a), for some r ? R}
c) Q’={q0}
d) All of the mentioned

10. e-transitions are
a) conditional
b) unconditional
c) input dependent
d) none of the mentioned

11. According to the precedence rules, x-y-z is equivalent to which of the following?
a) (x-y)-z
b) x-(y-z)
c) Both (x-y)-z and x-(y-z)
d) None of the mentioned

12. ____________ is used for grouping up of characters into token.
a) Lexical Analyzer
b) oolex
c) jflex
d) All of the mentioned

13. The minimum number of 1’s to be used in a regular expression of the given language:
R(x): The language of all strings containing exactly 2 zeroes.
a) 2
b) 3
c) 0
d) 1

14. a ^ nb ^ m where n >= 1, m >= 1, nm >= 3 is example of
a) Type 0
b) Type 1
c) Type 2
d) Type 3

15. Complement of (a + b)* will be
a) phi
b) null
c) a
d) b