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

View Answer

Answer: b
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

View Answer

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

View Answer

Answer: d
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

View Answer

Answer: b
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

View Answer

Answer:b
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

View Answer

Answer: b
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

View Answer

Answer: a
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

View Answer

Answer: a
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

View Answer

Answer: d
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

View Answer

Answer: b
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

View Answer

Answer: a
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

View Answer

Answer: d
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

View Answer

Answer: b
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

View Answer

Answer:d
Explanation: It is a regular expression.

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

View Answer

Answer:a
Explanation: Given expression accept all string so complement will accept nothing.

Related Articles

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to top button