MCQ Computer Science

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

1. The password to the admins account=”administrator”. The total number of states required to make a password-pass system using DFA would be __________
a) 14 states
b) 13 states
c) 12 states
d) A password pass system cannot be created using DFA

Explanation: For a string of n characters with no repetitive substrings, the number of states required to pass the string is n+1.
2.Let u=’1101’, v=’0001’, then uv=11010001 and vu= 00011101.Using the given information what is the identity element for the string?
a) u-1
b) v-1
c) u-1v-1
d) ε

Explanation: Identity relation: εw = wε = w, thus the one satisfying the given relation will be the identity element.
3. Number of states require to accept string ends with 10.
a) 3
b) 2
c) 1
d) can’t be represented.

Explanation: This is minimal finite automata.
4. If δ is the transition function for a given NFA, then we define the δ’ for the DFA accepting the same language would be:
Note: S is a subset of Q and a is a symbol.
a) δ’ (S, a) =Upϵs δ (p, a)
b) δ’ (S, a) =Up≠s δ (p, a)
c) δ’ (S, a) =Upϵs δ(p)
d) δ’ (S) =Up≠s δ(p)

Explanation: According to subset construction, equation 1 holds true.
5. If L is a regular language, Lc and Lr both will be:
a) Accepted by NFA
b) Rejected by NFA
c) One of them will be accepted
d) Cannot be said

Explanation: If L is a regular Language, Lc and Lr both are regular even.
6. 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.
7. Reverse of (0+1)* will be
a) Phi
b) Null
c) (0+1)*
d) (0+1)

Explanation: There is only one state which is start and final state of DFA so interchanging starting start and final state doesn’t change DFA.
8. (0+ε) (1+ε) represents
a) {0, 1, 01, ε}
b) {0, 1, ε}
c) {0, 1, 01 ,11, 00, 10, ε}
d) {0, 1}

Explanation: The regular expression is fragmented and the set of the strings eligible is formed. ‘+’ represents union while ‘.’ Represents concatenation.
9. (a + b*c) most correctly represents:
a) (a +b) *c
b) (a)+((b)*.c)
c) (a + (b*)).c
d) a+ ((b*).c)

Explanation: Following the rules of precedence, Kleene or star operation would be done first, then concatenation and finally union or plus operation.
10. Is it possible to obtain more than one regular expression from a given DFA using the state elimination method?
a) Yes
b) No

Explanation: Using different sequence of removal of state, we can have different possible solution of regular expressions. For n-state deterministic finite automata excluding starting and final states, n! Removal sequences are there. It is very tough to try all the possible removal sequences for smaller expressions.
11. Regular expressions are closed under
a) Union
b) Intersection
c) Kleen star
d) All of the mentioned

Explanation : According to definition of regular expression.
12. Which of the following do Regexps do not find their use in?
a) search engines
b) word processors
c) sed
d) none of the mentioned

Explanation: Regexp processors are found in several search engines, seach and replace mechanisms, and text processing utilities.
13. The action of parsing the source code into proper syntactic classes is known as:
a) Parsing
b) Interpretation analysis
c) Lexicography
d) Lexical Analysis

Explanation: Lexical analysis or scanning is the process of parsing the source code into proper syntactic classes. It gets things ready for the parser with lexemes to built the parse tree.
14. Which among the following is the closure property of a regular language?
a) Emptiness
b) Universality
c) Membership
d) None of the mentioned

Explanation: All the following mentioned are decidability properties of a regular language. The closure properties of a regular language include union, concatenation, intersection, Kleene, complement , reverse and many more operations.
15. If L is a language, the reversal of the language can be represented as:
a) L’
b) Lc
c) Lr
d) more than one option is correct