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
Explanation: The set of states which can be reached from q using e-transitions, is called the e-closure over state q.
a) Kleene, Union, Concatenate
b) Kleene, Star, Union
c) Kleene, Dot, Union
d) Star, Union, Dot
View Answer
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
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
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
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
Explanation : None.
7. Regular expression are
a) Type 0 language
b) Type 1 language
c) Type 2 language
d) Type 3 language
View Answer
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
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
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
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
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.
a) Recursive Inference
b) Derivations
c) Sentential forms
d) All of the mentioned
View Answer
Explanation: The following are the notions to express Context free grammars:
a) Recursive Inferences
b) Derivations
c) Sentential form
d) Parse trees
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
Explanation: We apply the productions of a CFG to infer that certain strings are in a language of certain variable.
a) Queue
b) Linked List
c) Tree
d) Hash Tables
View Answer
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
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.
