1. Which of the following is a correct statement?
a) { If an bn | n = 0,1, 2, 3 ..} is regular language
b) Strings with equal number of a’s and b’s denies a regular language
c) L (A* B*)∩ B gives the set A
d) None of the mentioned
Explanation: If we include A and B in a set and if we write A* it means except then A i.e. B same as B* means except then B i.e. so if we intersect (A*B*) and B then get A because in any regular language. If we write A-B then A-B=A intersection B’ so if we intersect A and B means A-B So the intersection of (A*B*) and B = (BA). intersection B means (BA)-B’ and B’=A so (BA) intersection(A)=A.
2. The classes of languages P and NP are closed under certain operations, and not closed under others. Decide whether P and NP are closed under each of the following operations.
1. Union
2. Intersection
3. Intersection with a regular language
4. Kleene closure (star)
5. Homomorphism
6. Inverse homomorphism
a) P is not closed under union
b) NP is not closed under intersection
c) None of the mentioned
d) P is not closed under union & NP is not closed under intersection
Explanation: Both P and NP are closed under each of these operations.
3. Ndfa and dfa accept same languages.
a) True
b) False
Explanation: They both are equivalent.
4. __________ a part of a compiler that is responsible for recognizing syntax.
a) Parser
b) Bzr
c) Linker
d) Optimizer
Explanation: Parser recognises all the syntax of the language.
5. __________ a part of a compiler that takes as input a stream of characters and produces as output a stream of words along with their associated syntactic categories.
a) Parser
b) Optimizer
c) Scanner
d) None of the mentioned
Explanation: A compiler’s scanner reads an input stream that consists of characters and produces an output stream that contains words, each labelled with its Syntactic category.
6. _________an IR-to-IR transformer that tries to improve the IR program in some way.
a) Optimizer
b) Parser
c) All of the mentioned
d) None of the mentioned
Explanation: The optimizer is an IR-to-IR transformer that tries to improve the IR program in some way.
7. _________ a phase of a compiler that maps the IR program into the instruction set and the finite resources of the target machine.
a) Optimizer
b) Parser
c) Optimizer & Parser
d) None of the mentioned
Explanation: In a two-phase compiler, ensures that there is a source program and an object program.
8. If the NFA N has n states, then the corresponding DFA D has 2n states.
a) True
b) False
Explanation: nfa has n then dfa has at max 2^n.
9. An NFA is nothing more than an ε-NFA with no ε transitions.
a) True
b) False
Explanation: An NFA is nothing more than an ε-NFA with no ε transitions. Thus • δ (q, ε) for all states q = ∅.
10. For every DFA, there is an ε-NFA that accepts the same language.
a) True
b) False
Explanation: For every DFA, there is an ε-NFA that accepts the same language and Vice Versa.