Virtual Labs

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

What is the main difference between a DFA and an NFA?

a: DFAs can accept more languages than NFAs Explanation

Explanation

b: NFAs can have multiple transitions for the same input symbol from a state Explanation

Explanation

c: DFAs require more memory than NFAs Explanation

Explanation

d: NFAs cannot have accept states Explanation

Explanation

How does an NFA decide to accept a string?

a: If all possible paths lead to accept states Explanation

Explanation

b: If at least one possible path leads to an accept state Explanation

Explanation

c: If the majority of paths lead to accept states Explanation

Explanation

d: If the first path explored leads to an accept state Explanation

Explanation

What is an epsilon (ε) transition in an NFA?

a: A transition that requires the empty string as input Explanation

Explanation

b: A transition that can be taken without consuming any input symbol Explanation

Explanation

c: A transition to the start state Explanation

Explanation

d: A transition that rejects the input Explanation

Explanation

Can a DFA be considered as a special case of an NFA?

a: No, they are completely different models Explanation

Explanation

b: Yes, every DFA is an NFA with exactly one transition per state-symbol pair Explanation

Explanation

c: Only if the DFA has no accept states Explanation

Explanation

d: Only if the DFA has epsilon transitions Explanation

Explanation

What happens when an NFA is in a state with no transition for the current input symbol?

a: The automaton crashes Explanation

Explanation

b: That computation path dies (is rejected) Explanation

Explanation

c: The automaton skips that symbol Explanation

Explanation

d: The automaton returns to the start state Explanation

Explanation

Do NFAs and DFAs recognize the same class of languages?

a: No, NFAs are more powerful Explanation

Explanation

b: No, DFAs are more powerful Explanation

Explanation

c: Yes, they both recognize exactly the regular languages Explanation

Explanation

d: It depends on whether epsilon transitions are allowed Explanation

Explanation

How should non-determinism in NFAs be understood?

a: As random choice between possible transitions Explanation

Explanation

b: As parallel exploration of all possible paths simultaneously Explanation

Explanation

c: As sequential trying of each path until one succeeds Explanation

Explanation

d: As choosing the shortest path to an accept state Explanation

Explanation

What is the role of multiple transitions on the same symbol in an NFA?

a: They create ambiguity that makes the NFA invalid Explanation

Explanation

b: They allow the NFA to explore multiple computational paths Explanation

Explanation

c: They must all lead to the same state Explanation

Explanation

d: They indicate an error in the NFA design Explanation

Explanation

Which statement about NFAs with epsilon transitions is correct?

a: They are more powerful than NFAs without epsilon transitions Explanation

Explanation

b: They can recognize non-regular languages Explanation

Explanation

c: They can be converted to equivalent NFAs without epsilon transitions Explanation

Explanation

d: They are required for accepting the empty string Explanation

Explanation

If an NFA has n states, what can we say about the number of possible computation paths for a string of length m?

a: Exactly m paths Explanation

Explanation

b: At most n paths Explanation

Explanation

c: Potentially exponential in m Explanation

Explanation

d: Exactly n^m paths Explanation

Explanation

What is the language of an NFA?

a: The set of all possible paths in the NFA Explanation

Explanation

b: The set of all strings that lead to at least one accept state Explanation

Explanation

c: The set of all strings that lead to all accept states Explanation

Explanation

d: The set of transitions in the NFA Explanation

Explanation

Why might NFAs be easier to design than DFAs for certain languages?

a: NFAs require fewer states in all cases Explanation

Explanation

b: NFAs allow more flexibility in modeling with multiple paths and epsilon transitions Explanation

Explanation

c: NFAs are always faster to simulate Explanation

Explanation

d: NFAs can accept more languages Explanation

Explanation

In an NFA, when processing an input string, what determines acceptance?

a: The first path that completes Explanation

Explanation

b: The longest path that completes Explanation

Explanation

c: Whether any path ends in an accept state after all input is consumed Explanation

Explanation

d: Whether the most likely path ends in an accept state Explanation

Explanation