MCQ Computer Science

# Automata Theory Multiple Choice Question & Answer (MCQs) Set-2

1. Assume the R is a relation on a set A, aRb is partially ordered such that a and b are _____________
a) reflexive
b) transitive
c) symmetric
d) reflexive and transitive

Explanation: A partially ordered relation refers to one which is Reflexive, Transitive and Antisymmetric.

2. In Moore machine, output is produced over the change of:
a) transitions
b) states
c) Both
d) None of the mentioned

Explanation: Moore machine produces an output over the change of transition states while mealy machine does it so for transitions itself.

3. An e-NFA is ___________ in representation.
b) Quintuple
c) Triple
d) None of the mentioned

Explanation: An e-NFA consist of 5 tuples: A=(Q, S, d, q0. F)
Note: e is never a member of S.

4. Extended transition function is .
a) Q * S* -> Q
b) Q * S -> Q
c) Q* * S* -> S
d) Q * S -> S

Explanation: This takes single state and string of input to produce a state.

5. For a DFA accepting binary numbers whose decimal equivalent is divisible by 4, what are all the possible remainders?
a) 0
b) 0,2
c) 0,2,4
d) 0,1,2,3

Explanation: All the decimal numbers on division would lead to only

4 remainders i.e. 0,1,2,3 (Property of Decimal division).

6. String X is accepted by finite automata if .
a) d*(q,x) E A
b) d(q,x) E A
c) d*(Q0,x) E A
d) d(Q0,x) E A

Explanation: If automata starts with starting state and after finite moves if reaches to final step then it called accepted.

7. Given Language L= {x? {a, b}*|x contains aba as its substring}
Find the difference of transitions made in constructing a DFA and an equivalent NFA?
a) 2
b) 3
c) 4
d) Cannot be determined.

Explanation: The individual Transition graphs can be made and the difference of transitions can be determined.

8. The construction time for DFA from an equivalent NFA (m number of node)is:
a) O(m2)
b) O(2m)
c) O(m)
d) O(log m)

Explanation: From the coded NFA-DFA conversion.

9. Which of the following is a regular language?
a) String whose length is a sequence of prime numbers
b) String with substring wwr in between
c) Palindrome string
d) String with even number of Zero’s

Explanation: DFSM’s for the first three option is not possible; hence they aren’t regular.

10. The total number of states to build the given language using DFA:
L= {w | w has exactly 2 a’s and at least 2 b’s}
a) 10
b) 11
c) 12
d) 13

Explanation: We need to make the number of a as fixed i.e. 2 and b can be 2 or more. Thus, using this condition a finite automata can be created using 1 states.

11. Which of the following is type 3 language ?
a) Strings of 0’s whose length is perfect square
b) Palindromes string
c) Strings of 0’s having length prime number
d) String of odd number of 0’s

Explanation: Only d is regular language.

12. The e-NFA recognizable languages are not closed under :
a) Union
b) Negation
c) Kleene Closure
d) None of the mentioned

Explanation: The languages which are recognized by an epsilon Non deterministic automata are closed under the following operations:
a) Union
b) Intersection
c) Concatenation
d) Negation
e) Star
f) Kleene closure

13. Which among the following is not an associative operation?
a) Union
b) Concatenation
c) Dot
d) None of the mentioned

Explanation: It does not matter in which order we group the expression with the operators as they are associative. If one gets a chance to group the expression, one should group them from left for convenience. For instance, 012 is grouped as (01)2.

14. Which of the following is the task of lexical analysis?
a) To build the uniform symbol table
b) To initialize the variables
c) To organize the variables in a lexical order
d) None of the mentioned

Explanation: Lexical analysis involves the following task:
a) Building a uniform symbol table
b) Parsing the source code into tokens
c) Building a literal and identifier table

15. The scanner outputs:
a) Stream of tokens
b) Image file
c) Intermediate code
d) Machine code