1. Which of the following options is correct?
Statement 1: Initial State of NFA is Initial State of DFA.
Statement 2: The final state of DFA will be every combination of final state of NFA.
a) Statement 1 is true and Statement 2 is true
b) Statement 1 is true and Statement 2 is false
c) Statement 1 can be true and Statement 2 is true
d) Statement 1 is false and Statement 2 is also false
View Answer
Explanation: Statement 1 and 2 always true for a given Language.
a) NFA
b) DFA
c) PDA
d) Can’t be said
View Answer
Explanation: We use the construction method to prove the validity of closure properties of regular languages. Thus, it can be observe, how tedious and complex is the construction of a DFA as compared to an NFA with respect to space.
a) 16
b) 11
c) 5
d) 6
View Answer
Explanation: If L leads to FA1, then for Lc, the FA can be obtained by exchanging the final and non-final states.
a) Union
b) Negation
c) Kleene Closure
d) None of the mentioned
View Answer
a) Union
b) Intersection
c) Concatenation
d) Negation
e) Star
f) Kleene closure
5. If L1 is regular L2 is unknown but L1-L2 is regular ,then L2 must be
a) Empty set
b) CFG
c) Decidable
d) Regular
View Answer
Explanation: Regular is closed under difference.
6. The given NFA represents which of the following NFA
a) (ab U a) *
b) (a*b* U a*)
c) (ab U a*)
d) (ab)* U a*
View Answer
Explanation: The Regular expression (ab U a) * is converted to NFA in a sequence of stages as it can be clearly seen in the diagram. This NFA consist of 8 stated while its minimized form only contains 2 states.
7. The behaviour of NFA can be simulated using DFA.
a) always
b) never
c) sometimes
d) none of the mentioned
View Answer
Explanation: For every NFA, there exists an equivalent DFA and vice versa.
8. FL is equivalent to
a) LF
b) F
c) L
d) ?
View Answer
Explanation : None.
9. L and ~L are recursive enumerable then L is
a) Regular
b) Context free
c) Context sensitive
d) Recursive
View Answer
Explanation :If L is recursive enumerable and its complement too if and only if L is recursive.
10. Which of the following does not support regular expressions?
a) sed
b) awk
c) emacs
d) none of the mentioned
View Answer
Explanation: There are many UNIX tools including vi, Emacs, sed, awk and modern programming languages which support regular expressions.
11. Which of the following characters are ignored while lexical analysis?
a) .
b) =
c) #
d) WhiteSpace
View Answer
Explanation: The lexical analyzer ignores all the whitespaces and fragments the program into tokens.
a) 2
b) 5
c) 3
d) 6
View Answer
Explanation: We select a string w such that w=xyz and |y|>0 and other conditions. However, there exists an integer n such that |w|>=n for any wÎL.
13. State true or false:
Statement: Pumping lemma gives a necessary but not sufficient condition for a language to be regular.
a) true
b) false
View Answer
Explanation: The converse of the lemma is not true. There may exists some language which satisfy all the conditions of the lemma and still be non-regular.
a) Softball team
b) Sock picking
c) Hair counting
d) All of the mentioned
View Answer
Explanation: There are several applications of pigeonhole principle:
Example: The softball team: Suppose 7 people who want to play softball(n=7 items), with a limitation of only 4 softball teams to choose from. The pigeonhole principle tells us that they cannot all play for different teams; there must be atleast one team featuring atleast two of the seven players.
a) regular
b) non regular
c) may be regular
d) none of the mentioned
View Answer
Explanation: If A and B are regular languages, then A Ç B is a regular language and A n B is equivalent to !(A’ U B’).
