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?
Find the states traversed from the given diagram
a) A B
b) C
c) C D
d) D A
View Answer

Answer: c
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?
Find the suffix of s from the given diagram
a) 111001
b) 111111
c) 111000
d) 101010
View Answer

Answer: a
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

Answer: d
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

Answer: d
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

Answer: a
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

Answer: a
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

Answer: d
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?
Find the rightmost derivation from the given diagram
a) aAbAba
b) aababa
c) aABba
d) aSba
View Answer

Answer: b
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

Answer: c
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

Answer: a
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.

Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.