MCQ Computer Science

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

Explanation: Finite automaton with an output is categorize din two parts: Moore M/C and Mealy M/C.

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

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

Explanation: A DFA can be represented in the following formats: Transition Graph, Transition Table, Transition tree/forest/Any programming Language.

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

Explanation: Here, d refers to transition function and results into new state or function when an transition is performed over its state.

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

Explanation: First it parse y string after that it parse a.

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

Explanation: DFA is a specific case of NFA.

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

Explanation: We can represent one language in more one FSMs, example for a same language we have a DFA and an equivalent NFA.

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

Explanation: If K is the number of states in NFA, the DFA simulating the same language would have states equal to or less than 2k.

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

Explanation: All the optioned mentioned are the instruction formats of how to convert a NFA to a DFA.

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

Explanation: An epsilon move is a transition from one state to another that doesnt require any specific condition.

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

Explanation: In arithmetic, we group two of the same operators from the left, hence x-y-z is equivalent to (x-y)-z and not x-(y—z).

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

Explanation: oolex, flex, lex, jflex, all are lexical analyzer tools which perform the following function.

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

Explanation: It is not required to automate the question if asked theoretically.The number of zeroes fixed is 2. Therefore, we can represent the regular expression as 1*01*01*.

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

Explanation: It is a regular expression.

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