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

View Answer

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

View Answer

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

View Answer

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

View Answer

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

View Answer

Answer: a
Explanation: If L is a regular Language, Lc and Lr both are regular even.
6. An e-NFA is ___________ in representation.
a) Quadruple
b) Quintuple
c) Triple
d) None of the mentioned

View Answer

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

View Answer

Answer:c
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}

View Answer

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

View Answer

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

View Answer

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

View Answer

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

View Answer

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

View Answer

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

View Answer

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

View Answer

Answer: c
Explanation: Lr is defined as the reversal of a language. Lr is a set of strings whose reversal is in L.
Example: L={0, 01, 100}
Lr={0, 10, 001}

Related Articles

Leave a Reply

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

Check Also
Close
Back to top button