NFA_flashcards
What is a key property of a DFA state regarding transitions?
Every state has exactly one outgoing arrow for each symbol in Σ.
How is the next state in a DFA determined?
Completely by the current state and input symbol.
Why is having two transitions on the same symbol from one state illegal in DFAs?
Because it violates the rule that each symbol leads to exactly one state.
Are ε-moves allowed in DFAs?
No, ε-moves are not allowed in DFAs but are allowed in NFAs.
What is the formal definition of an NFA?
A 5-tuple A = (Q, Σ, Δ, s, F).
What does Q represent in an NFA?
A finite set of states.
What does Σ represent in an NFA?
The input alphabet.
What does Δ represent in an NFA?
The transition relation, Δ ⊆ Q × (Σ ∪ {ε}) × Q.
What is an alternative definition of the transition function in an NFA?
δ: Q × (Σ ∪ {ε}) → P(Q), where P(Q) is the powerset of Q.
What does s represent in an NFA?
The start state, s ∈ Q.
What does F represent in an NFA?
The set of accepting states, F ⊆ Q.
What is an example of a transition using ε in an NFA?
(q₁, ε, q₃).
How do NFAs work informally?
They try all possible ways of reading the input and accept if any computation path ends in an accepting state.
What must exist for an NFA to accept a word w?
A sequence y₁…yₙ ∈ Σ ∪ {ε} such that w = y₁…yₙ, and a sequence of states r₀…rₙ with r₀ = s, transitions in Δ, and rₙ ∈ F.
Why are NFAs useful?
They are easier to construct for many languages and allow powerful constructions like union and intersection.
Can DFAs be simulated by NFAs?
Yes, any DFA can be simulated by an NFA.
What is an example of a language that is easier to define using an NFA?
L₁ = { w ∈ {0,1} | w contains 1 in the third position from the end }.
