Nondeterministic finite automata
Prof. Dr. Mirco Schoenfeld
Recap
Last session was about finite state automata (FSA).
Recap
As a special form of FSA, we introduced
deterministic state
automata (DSA).
Regex matching with DFA
Can we model complex pattern using DFA?
Regex matching with DFA
Goddard (2024)
This matches all strings that end with ‘00’.
Regex matching with DFA
Goddard (2024)
Each of its transitions is uniquely determined by its source state
and input symbol, and reading an input symbol is required for each state
transition.
Regex matching with NFA
Goddard (2024)
This matches all strings that end with ‘101’.
Regex matching with NFA
Goddard (2024)
This is also a nondeterministic finite-state machine
(NFA).
What is the difference to the DFA?
Differences between DFA and NFA
Each NFA can be translated to an DFA.
A DFA can be seen as a special kind of NFA.
Differences between DFA and NFA
The main difference between DFA and NFA is in transition function
\(\delta\):
\(\delta : Q \times \Sigma \rightarrow
P(Q)\)
\(\delta\) now allows a set
of possible states to transition to.
Differences between DFA and NFA
In other words, NFA can have zero, one, or multiple transitions
corresponding to a particular symbol.
Nondeterministic finite automaton
A NFA \(M\) is a 5-tuple, \(( Q, \Sigma, \delta , q_0 , F)\),
consisting of
- a finite set of states \(Q\)
- a finite set of input symbols called the alphabet
\(\Sigma\)
- a transition function \(\delta : Q \times \Sigma \rightarrow
P(Q)\)
- an initial or start state \(q_0 \in Q\)
- a set of accept states \(F \subseteq Q\)
Differences between DFA and NFA
The conditions for when a NFA matches remain the same:
- \(r_0 = q_0\)
- \(r_{i+1} = \delta_{(r_i, a_{i+1})}
\text{for } i = 0,\ldots,n-1\)
- \(r_n \in F\).
Regex matching with NFA
Goddard
(2024)
Where the NFA has more than one possible transitions, it
branches
Regex matching with NFA
Nondeterminism can be thought of a tree growing downwards:
Goddard
(2024)
If at least one branch leads to an accept state, the input is
accepted.
FSA enable automation
Goddard
(2024)
Acknowledgement
Acknowledgement:
This script is inspired by Goddard (2024).
