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

View Answer

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

View Answer

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

View Answer

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

View Answer

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

View Answer

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

View Answer

Answer : c,d
Explanation : None.

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

View Answer

Answer : a
Explanation : According to Chomsky hierarchy .

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

View Answer

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

View Answer

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

View Answer

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

View Answer

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

View Answer

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

View Answer

Answer: a
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
b) Linked List
c) Tree
d) Hash Tables

View Answer

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

View Answer

Answer: a
Explanation: It is the parse tree theorem which states:
Given: Suppose we have a parse tree for a string w, according to a CNF grammar, G=(V, T, P, S). Let h be the height of the parse tree. Now, Implication: |w|<=2h-1.

Related Articles

Leave a Reply

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

Back to top button