Virtual Labs

Language acceptance for Non-deterministic Finite State Automata (NFAs)

What is the subset construction algorithm used for?

a: Converting a DFA to an NFA Explanation

Explanation

b: Converting an NFA to a DFA Explanation

Explanation

c: Minimizing the number of states in an NFA Explanation

Explanation

d: Finding the complement of an NFA Explanation

Explanation

In the worst case, how many states might a DFA have when converted from an NFA with n states?

a: n states Explanation

Explanation

b: n² states Explanation

Explanation

c: 2ⁿ states Explanation

Explanation

d: n! states Explanation

Explanation

How do you eliminate epsilon transitions from an NFA?

a: Remove all epsilon transitions and their target states Explanation

Explanation

b: Replace epsilon transitions with regular transitions Explanation

Explanation

c: Compute epsilon closure and add direct transitions Explanation

Explanation

d: Convert the NFA to a DFA first Explanation

Explanation

What is the epsilon closure of a state in an NFA?

a: The set of states reachable by epsilon transitions only Explanation

Explanation

b: The set of states that can reach the given state by epsilon transitions Explanation

Explanation

c: The set of all states in the NFA Explanation

Explanation

d: The set of accept states reachable by epsilon transitions Explanation

Explanation

Which of the following operations is NOT closed under regular languages?

a: Union Explanation

Explanation

b: Intersection Explanation

Explanation

c: Complement Explanation

Explanation

d: Context-free intersection Explanation

Explanation

What is the time complexity of simulating an NFA with n states on an input string of length m?

a: O(m) Explanation

Explanation

b: O(mn) Explanation

Explanation

c: O(mn²) Explanation

Explanation

d: O(2ⁿm) Explanation

Explanation

In practical applications, why might NFAs be preferred over DFAs despite their non-determinism?

a: NFAs are always faster to execute Explanation

Explanation

b: NFAs require less memory Explanation

Explanation

c: NFAs are often more compact and easier to construct Explanation

Explanation

d: NFAs can recognize more languages Explanation

Explanation

What happens during the subset construction when an NFA state has no outgoing transition for a given input symbol?

a: The construction fails Explanation

Explanation

b: A dead state is created in the DFA Explanation

Explanation

c: The input symbol is ignored Explanation

Explanation

d: That state is not included in the current subset Explanation

Explanation

Which statement about the relationship between regular expressions and NFAs is correct?

a: Every regular expression can be converted to an equivalent NFA Explanation

Explanation

b: Every NFA can be converted to an equivalent regular expression Explanation

Explanation

c: Regular expressions and NFAs have equivalent expressive power Explanation

Explanation

d: All of the above Explanation

Explanation