MCQ Computer Science

# Automata Theory Multiple Choice Quaestion & Answers (MCQs) set-27

1. According to the given transitions, which among the following are the epsilon closures of q1 for the given NFA?
? (q1, e) = {q2, q3, q4}
? (q4, 1) =q1
? (q1, e) =q1
a) q4
b) q2
c) q1
d) q1, q2, q3, q4

Explanation: The set of states which can be reached from q using e-transitions, is called the e-closure over state q.

2. The appropriate precedence order of operations over a Regular Language is
a) Kleene, Union, Concatenate
b) Kleene, Star, Union
c) Kleene, Dot, Union
d) Star, Union, Dot

Explanation: If a regular language expression is given, the appropriate order of precedence if the parenthesis is ignored is: Star or Kleene, Dot or Concatenation, Union or Plus.

3. The __________ of a set of states, P, of an NFA is defined as the set of states reachable from any state in P following e-transitions.
a) e-closure
b) e-pack
c) Q in the tuple
d) None of the mentioned

Explanation: The e-closure of a set of states, P, of an NFAis defined as the set of states reachable from any state in P following e-transitions.

4. If L1 and L2 are regular sets then intersection of these two will be
a) Regular
b) Non Regular
c) Recursive
d) Non Recursive

Explanation: Regular expression are also colsed under intersection.

5. Generate a regular expression for the following problem statement:
Password Validation: String should be 8-15 characters long. String must contain a number, an Uppercase letter and a Lower case letter.
a) ^(?=.*[a-z])(?=.*[A-Z])(?=.*\d).{8,15}\$
b) ^(?=.*[a-z])(?=.*[A-Z])(?=.*\d).{9,16}\$
c) ^(?=.[a-z])(?=.[A-Z])(?=.\d).{8,15}\$
d) None of the mentioned

Explanation: Passwords like abc123, 123XYZ, should not be accepted . If one also wants to include special characters as one of the constraint, one can use the following regular expression:
^(?=.*[a-z])(?=.*[A-Z])(?=.*\d)(?=.*[^\da-za-Z]).{8,15}\$

6. ?L is equivalent to
a) ?
b) F
c) L
d) L?

Explanation : None.

7. Regular expression are
a) Type 0 language
b) Type 1 language
c) Type 2 language
d) Type 3 language

Explanation : According to Chomsky hierarchy .

8. Language of finite automata is.
a) Type 0
b) Type 1
c) Type 2
d) Type 3

Explanation: According to Chomsky classification.

9. If n is the length of Input string and m is the number of nodes, the running time of DFA is x that of NFA.Find x?
a) 1/m2
b) 2m
c) 1/m
d) log m

Explanation: Running time of DFA: O(n) and Running time of NFA =O(m2n).

10. Finite state machine are not able to recognize Palindromes because:
a) Finite automata cannot deterministically find the midpoint
b) Finite automata cannot remember arbitarily large amount of data
c) Even if the mid point is known, it cannot find whether the second half matches the first
d) All of the mentioned

Explanation: It is the disadvantage or lack of property of a DFA that it cannot remember an arbitrarily such large amount of data which makes it incapable of accepting such languages like palindrome, reversal, etc.

11. The entity which generate Language is termed as:
a) Automata
b) Tokens
c) Grammar
d) Data

Explanation: The entity which accepts a language is termed as Automata while the one which generates it is called Grammar. Tokens are the smallest individual unit of a program.

12. Which of the following is not a notion of Context free grammars?
a) Recursive Inference
b) Derivations
c) Sentential forms
d) All of the mentioned

Explanation: The following are the notions to express Context free grammars:
a) Recursive Inferences
b) Derivations
c) Sentential form
d) Parse trees

13. Choose the correct option:
Statement: There exists two inference approaches:
a) Recursive Inference
b) Derivation
a) true
b) partially true
c) false
d) none of the mentioned

Explanation: We apply the productions of a CFG to infer that certain strings are in a language of certain variable.

14. The most suitable data structure used to represent the derivations in compiler:
a) Queue
c) Tree
d) Hash Tables

Explanation: The tree, known as “Parse tree” when used in a compiler, is the data structure of choice to represent the source program.

15. State true or false:
Statement: A CNF parse tree’s string yield (w) can no longer be 2h-1.
a) true
b) false