This set of Compilers Multiple Choice Questions & Answers (MCQs) focuses on “Transformation from NFA to DFA – 2”.

1. A deterministic finite automation (DFA)D with alphabet ∑= {a,b} is given below

Which of the following is a valid minimal DFA which accepts the same language as D?

a)

b)

c)

d)

View Answer

Explanation: Options (B) and (C) are invalid because they both accept ‘b’ as a string which is not accepted by give DFA. D is invalid because it accepts bb+a which are not accepted by given DFA.

2. The lexical analysis for a modern language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?

a) Finite state automata

b) Deterministic pushdown automata

c) Non-deterministic pushdown automata

d) Turing machine

View Answer

Explanation: Initially in lexical analysis the program is divided into tokens. Tokens can be expressed as regular expressions: [a-zA-Z] [a-zA-Z0-9]*

the keyword if is given by if.

Integers are given by [+-]? [0-9]+.

3. Is empty string a valid input in Ndfa

a) True

b) False

View Answer

Explanation: Empty strings can be inputted n a NDFA.

4. What is the complement of the language accepted by the NFA shown below? Assume ∑ = {a} and ε is the empty string

a) Φ

b) ε

c) a

d) {a, ε}

View Answer

Explanation: The given alphabet ∑ contains only one symbol {a} and the given NFA accepts all strings with any number of occurrences of ‘a’. Hence the complement is an empty string.

5. Given the language L = {ab, aa, baa}, whih of the following strings are in L*?

1) abaabaaabaa

2) aaaabaaaa

3) baaaaabaaaab

4) baaaaabaa

a) 1, 2 and 3

b) 2, 3 and 4

c) 1, 2 and 4

d) 1, 3 and 4

View Answer

Explanation: Any combination of strings in set {ab, aa, baa} will be in L*.

“abaabaaabaa” can be partitioned as a combination of strings in set {ab, aa, baa}. The partitions are “ab aa baa ab aa”

2) “aaaabaaaa” can be partitioned as a combination of strings in set {ab, aa, baa}. The partitions are “aa ab aa aa”

3) “baaaaabaaaab” cannot be partitioned as a combination of strings in set {ab, aa, baa}

4) “baaaaabaa” can be partitioned as a combination of strings in set {ab, aa, baa}. The partitions are “baa aa ab aa”.

6. Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. Complete the partially completed DFA that accepts this language is shown below.

The missing arcs in the DFA are

a)

b)

c)

d)

View Answer

Explanation: State ‘q’ is trap state. All other states are accepting states. In state 00, DFA must move to ‘q’ for input symbol 0. All (non-trap) states indicate names indicate the characters seen before reaching that particular state. Option (D) is the only options that follow these rules.

7. Which of the following problems occur?

1) Does a given program ever produce an output?

2) If L is a CFL, then is L’ is also context-free?

3)L’ is regular only if L is regular?

4) If L is a recursive language, then, L’ is also recursive?

a) 1, 2, 3, 4

b) 1, 2

c) 2, 3, 4

d) 3, 4

View Answer

Explanation: 1) Is a variation of Turing Machine Halting problem and it is undecidable.

….2) Context Free Languages are not closed under intersection and complement.

….3) Complement of Regular languages is also regular.

….4) Recursive Languages is closed under complement.

8. Definition of a language L with alphabet {a} is given as following. L= { ank | k > 0, and n is a positive integer constant} What is the minimum number of states needed in a DFA to recognize L?

a) k+1

b) n+1

c) 2n+1

d) 2k+1

View Answer

Explanation: Note that n is a constant and k is any positive integer. For example, let n=3, then the DFA must be able to accept aaa, aaaaaa, aaaaaaaaa, , .. build such a DFA, 4 states are required.

**Sanfoundry Global Education & Learning Series – Compilers.**

To practice all areas of Compilers, __here is complete set of 1000+ Multiple Choice Questions and Answers__.