SI342: Reminder of how DFAs were developed

Defintion (DFA): A deterministic finite automaton is a 5-tuple (Q,Σ,δ,s,W), where

Q is the set of states (must be finite!)
Σ is the alphabet (must be finite!)
δ is a function, δ: Q x Σ → Q, defining the transitions
s is the start state, s ∈ Q
W is the set of accepting states, W ⊆ Q

Defintion (configuration): A configuration of machine M = (Q,Σ,δ,s,W) is a tuple (q,w) ∈ Q x Σ*. It is interpreted as "Machine M is in state q with string w left on the input tape".

Defintion ($\Rightarrow$): For machine M = (Q,Σ,δ,s,W), we say that configuration (p,v) yields in one step configuration (q,w) if for some character a ∈ Σ we have v = aw and δ(p,a) = q. This is sometimes denoted (p,v) ⇒ (q,w), or (p,v) ⇒_M (q,w) when you need to clearly indicate which machine you're referring to.

Defintion ($\Rightarrow^*$): For machine M = (Q,Σ,δ,s,W), we say that configuration (p,v) yields configuration (q,w) if there is a sequence of configurations (q1,w1), (q2,w2), ..., (qk,wk) such that

(p,v) = (q1,w1) ⇒ (q2,w2) ⇒ ... ⇒ (qk,wk) = (q,w)

This is sometimes denoted (p,v) ⇒* (q,w), or (p,v) ⇒*_M (q,w) when you need to clearly indicate which machine you're referring to.

Defintion (accept): Machine M = (Q,Σ,δ,s,W) accepts string w ∈ Σ* if configuration (s,w) ⇒* (q,λ) for some state q ∈ W.