Finite automata (DFA and NFA) in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Difference between DFA and NFA

Which of the following statements correctly describes a key difference between a Deterministic Finite Automaton (DFA) and a Nondeterministic Finite Automaton (NFA)?

A A DFA has exactly one transition for each symbol from every state, while an NFA can have zero, one, or multiple transitions for the same symbol from a state.

B An NFA requires more memory than a DFA because it stores all possible states simultaneously.

C A DFA can accept languages that an NFA cannot accept.

D An NFA always has fewer states than a DFA for the same language.

💡 Hint

Think about how transitions are defined for each input symbol in DFA and NFA.

A DFA has exactly one transition for each input symbol from every state, making its behavior deterministic. An NFA can have multiple or no transitions for the same symbol, allowing multiple possible next states.

📋 Factual

intermediate

Number of states in equivalent DFA

Given an NFA with 3 states, what is the maximum number of states in an equivalent DFA constructed from it?

A 6

B 3

C 8

D 9

💡 Hint

Consider the subset construction method for converting an NFA to a DFA.

The subset construction method creates states in the DFA corresponding to subsets of NFA states. For 3 NFA states, the maximum subsets are 2^3 = 8.

🔍 Analysis

advanced

Language acceptance by NFA with epsilon transitions

Consider an NFA with epsilon (ε) transitions. Which of the following statements about its language acceptance is true?

A Epsilon transitions require the NFA to have more states than a DFA for the same language.

B Epsilon transitions increase the class of languages the NFA can accept beyond regular languages.

C Epsilon transitions make the NFA equivalent to a pushdown automaton.

D The NFA can accept a string without consuming any input symbols by using epsilon transitions alone.

💡 Hint

Think about what epsilon transitions allow the automaton to do without reading input.

Epsilon transitions allow the NFA to move between states without consuming input symbols, so it can accept the empty string or move freely before reading input.

❓ Comparison

advanced

Equivalence of DFA and NFA

Which statement best describes the equivalence between DFAs and NFAs?

A Every NFA has an equivalent DFA that accepts the same language, but the DFA may have exponentially more states.

B NFAs can accept some languages that no DFA can accept.

C Every DFA has an equivalent NFA that accepts a strictly larger set of languages.

D DFAs and NFAs accept exactly the same number of states for any language.

💡 Hint

Consider the power set construction and language classes accepted by both automata.

DFAs and NFAs accept exactly the same class of languages (regular languages). Every NFA can be converted to an equivalent DFA, but the DFA may have exponentially more states.

❓ Reasoning

expert

Minimization impact on DFA states

You have a DFA with 16 states recognizing a certain regular language. After minimization, the DFA has 5 states. Which of the following is a valid conclusion?

A The minimized DFA accepts a different language with fewer states.

B The original DFA had redundant states that did not affect the language recognized.

C Minimization can only reduce states if the language is finite.

D The minimized DFA must have more states than any equivalent NFA.

💡 Hint

Think about what minimization does to a DFA and the language it accepts.

Minimization removes states that are equivalent or unreachable, reducing the DFA size without changing the language it accepts.