This set of Compilers Multiple Choice Questions & Answers (MCQs) focuses on “The NFA with n-moves to the DFA – 1”.
1. Examine the following DFA: If input is 011100101, which edge is NOT traversed?
a) A B
b) C
c) C D
d) D A
View Answer
Explanation: The states traversed are ABDBDABDAC, and the only edge not traversed C D.
2. If string s is accepted by this DFA, which of these strings cannot be suffix of s?
a) 111001
b) 111111
c) 111000
d) 101010
View Answer
Explanation: 111001 cannot be the suffix of any string accepted by this DFA. Suppose s=w111001. No matter what state the DFA reaches after reading w, it will go to state D after reading “111”, then go to state B after reading “00” and finally reaches state C after reading “1”.
3. Find the pair of regular expressions that are equivalent.
a) (0+1)* and (0*+1*)*
b) (0+1)* and (0+1*)*
c) (0+10)* and (0*+10)*
d) All of the mentioned
View Answer
Explanation: All generate all strings of 0’s and 1’s thus are these pairs are equivalent.
4. Which of the following strings is NOT in the Kleene star of the language {011, 10, 110}?
a) 01
b) 10
c) 110
d) 10011101
View Answer
Explanation: Every string in the language {011, 10, 110}* has to be formed from zero or more uses of the strings 011, 10, and 110. A string may be used more than once.
5. Which grammar is not regular?
a) 0^n
b) 0^n 1^n n
c) 0^m 0^n n
d) 0^n 0^n n
View Answer
Explanation: According to pumping lemma, is not a regular language. It is the language of the DFA with two states to achieve an even number of 0’s…
6. If is a language, and is a symbol, then, the quotient of and, is the set of strings such that is in: is in. Suppose is regular, which of the following statements is true?
a) L/a is always a regular language
b) L/a is not a regular language
c) All of the mentioned
d) None of the mentioned
View Answer
Explanation: We can build a DFA for as such: firstly we get the DFA for: Then, we copy all the states and transitions to the DFA for. However, we mark any state as a final state in if and only if is a final state in.
7. Here is a context-free grammar G: S → AB A → 0A1 | 2 B → 1B | 3A which of the following strings are in L (G)?
a) 021300211
b) 022111300211
c) None of the mentioned
d) 021300211 & 022111300211
View Answer
Explanation: First, notice that A generates strings of the form 021, where n is 0 or more. Also, B gives zero or more 1’s, which is followed by one 3, and then A gives something. Since S generates something an A can generate followed by something a B can generate, the strings in L (G) are of the form 0 21 30 21.
8. The parse tree below represents a rightmost derivation according to the grammar S → AB, A → aS|a, B → bA. Which of the following are right-sentential forms corresponding to this derivation?
a) aAbAba
b) aababa
c) aABba
d) aSba
View Answer
Explanation: S => AB => AbA => Aba => aSba => aABba => aAbAba => aAbaba => aababa.
9. The grammar G: S → SS | a | b is ambiguous. Check all and only the strings that have exactly two leftmost derivations in G.
a) bbb
b) ab
c) All of the mentioned
d) None of the mentioned
View Answer
Explanation: S => a. A string of length 2 has only one derivation, e.g., S => SS => aS => ab.
10. For the following grammar: S → A | B | 2 A → C0 | D B → C1 | E C → D | E | 3 D → E0 | S E → D1 | S Identify all the unit pairs.
a) D,C
b) A,B
c) B,C
d) A,C
View Answer
Explanation: The cycle of unit-productions S → A → D → S says that any pair involving only S, A, and D is a unit pair. Similarly, the cycle S → B → E → S tells us that any pair involving S, B, and E is a unit pair.
Sanfoundry Global Education & Learning Series – Compilers.
To practice all areas of Compilers, here is complete set of 1000+ Multiple Choice Questions and Answers.
- Practice MCA MCQs
- Check Compiler Design Books
- Practice Computer Science MCQs
- Apply for Computer Science Internship
- Check Computer Science Books
