Virtual Labs

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

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

a: DFA has more states than NFA Explanation

Explanation

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

Explanation

c: DFA can handle epsilon transitions while NFA cannot Explanation

Explanation

d: NFA is faster than DFA Explanation

Explanation

In the formal definition of NFA, what does the transition function δ map to?

a: A single state Q Explanation

Explanation

b: The power set of states P(Q) Explanation

Explanation

c: A pair of states Explanation

Explanation

d: The alphabet Σ Explanation

Explanation

What are epsilon (ε) transitions in an NFA?

a: Transitions that require no input symbol Explanation

Explanation

b: Transitions that only accept empty strings Explanation

Explanation

c: Transitions that lead to reject states Explanation

Explanation

d: Transitions that are not allowed in NFAs Explanation

Explanation

How does an NFA handle multiple possible transitions from a state?

a: It chooses the first transition randomly Explanation

Explanation

b: It splits into multiple copies and explores all possibilities in parallel Explanation

Explanation

c: It rejects the input immediately Explanation

Explanation

d: It chooses the transition that leads to an accept state Explanation

Explanation

When does an NFA accept a string?

a: When all computation paths lead to accept states Explanation

Explanation

b: When at least one computation path leads to an accept state Explanation

Explanation

c: When the majority of computation paths lead to accept states Explanation

Explanation

d: When no computation path leads to a reject state Explanation

Explanation

What happens when an NFA encounters an input symbol for which there is no transition from the current state?

a: The entire machine rejects the string Explanation

Explanation

b: The machine waits for the next input symbol Explanation

Explanation

c: That particular copy of the machine dies Explanation

Explanation

d: The machine transitions to the start state Explanation

Explanation

What is the relationship between NFAs and DFAs in terms of computational power?

a: NFAs are more powerful than DFAs Explanation

Explanation

b: DFAs are more powerful than NFAs Explanation

Explanation

c: NFAs and DFAs have equivalent computational power Explanation

Explanation

d: NFAs and DFAs are incomparable Explanation

Explanation

What is a regular language?

a: A language that follows regular patterns Explanation

Explanation

b: A language that is recognized by some finite state machine Explanation

Explanation

c: A language with a finite number of strings Explanation

Explanation

d: A language that uses only regular expressions Explanation

Explanation

In the context of NFAs, what does 'non-determinism' mean?

a: The machine makes random choices Explanation

Explanation

b: The machine cannot determine the correct path Explanation

Explanation

c: There can be multiple valid transitions for the same input Explanation

Explanation

d: The machine always rejects input Explanation

Explanation