# Compilers Questions and Answers – The NFA with n-moves to the DFA – 1

«
»

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

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

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

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

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

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

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

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

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

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

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. 