Virtual Labs

NFA to DFA Conversion using Subset Construction

What does NFA stand for?

a: Non-deterministic Finite Automaton Explanation

Explanation

b: New Finite Automaton Explanation

Explanation

c: Normal Finite Automaton Explanation

Explanation

d: Nested Finite Automaton Explanation

Explanation

Which of the following is a key difference between NFA and DFA?

a: DFA has more states than NFA Explanation

Explanation

b: NFA can have multiple transitions from one state on the same input Explanation

Explanation

c: DFA uses a different alphabet Explanation

Explanation

d: NFA cannot have accepting states Explanation

Explanation

What are epsilon (ε) transitions in an NFA?

a: Transitions that consume input symbols Explanation

Explanation

b: Transitions that don't consume any input symbol Explanation

Explanation

c: Transitions to accepting states only Explanation

Explanation

d: Transitions that reject the input Explanation

Explanation

What is the epsilon closure of a set of states?

a: The set of states reachable using only input symbols Explanation

Explanation

b: The set of all accepting states Explanation

Explanation

c: The set of states reachable using only epsilon transitions Explanation

Explanation

d: The set of states that reject input Explanation

Explanation

In the subset construction algorithm, each DFA state represents:

a: A single NFA state Explanation

Explanation

b: A subset of NFA states Explanation

Explanation

c: A transition in the NFA Explanation

Explanation

d: An input symbol Explanation

Explanation

When is a DFA state considered accepting in the subset construction?

a: When it contains only accepting NFA states Explanation

Explanation

b: When it contains at least one accepting NFA state Explanation

Explanation

c: When it is the start state Explanation

Explanation

d: When it has no outgoing transitions Explanation

Explanation

What is the time complexity of the subset construction algorithm in the worst case?

a: O(n) Explanation

Explanation

b: O(n²) Explanation

Explanation

c: O(2^n) Explanation

Explanation

d: O(n log n) Explanation

Explanation

Which statement about DFA minimization is correct?

a: All DFAs can be minimized to have exactly one state Explanation

Explanation

b: DFA minimization always reduces the number of states Explanation

Explanation

c: The minimized DFA accepts a different language than the original Explanation

Explanation

d: DFA minimization removes equivalent states while preserving the accepted language Explanation

Explanation

What is the relationship between the languages accepted by an NFA and its equivalent DFA?

a: The DFA accepts a subset of the NFA's language Explanation

Explanation

b: The NFA accepts a subset of the DFA's language Explanation

Explanation

c: They accept exactly the same language Explanation

Explanation

d: They accept completely different languages Explanation

Explanation