Machina ex RegEx
Prof. Dr. Mirco Schoenfeld
From Regex to machines
Today, we will introduce a system that
can evaluate
regular expressions.
Finite-state automata
Such systems are called Finite-state automata (FSA)
or simply state machines.
Finite-state automata
An FSA is an abstract machine that can be in
exactly one
of a finite number of states at any given time.
FSA can change from one state to another in response to inputs.
Finite-state automata
Finite-state automata have
- little computational power
- their memory limited to the number of states
- no functionality to write their state
persistently
Deterministic finite state machine
In deterministic finite state machines, deterministic refers
to the uniqueness of the computation run.
Transitions between states happen deterministically.
Deterministic finite state machine
A DFA \(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
Q\)
- an initial or start state \(q_0 \in Q\)
- a set of accept states \(F \subseteq Q\)
Deterministic finite state machine
How do DFA relate to this?
Regex matching with DFA
Let’s consider a string \(w = a_1a_2 \ldots
a_n\) over an alphabet \(\Sigma\).
Regex matching with DFA
The DFA \(M\) will accept
the string \(w\), i.e. indicate a
match, if there exists a sequence of states \(r_0, r_1, \ldots , r_n\) in \(Q\) with the following conditions:
- \(r_0 = q_0\)
- \(r_{i+1} = \delta_{(r_i,
a_{i+1})} \text{for } i = 0,\ldots,n-1\)
- \(r_n \in
F\).
Otherwise the string is rejected.
To be continued
…to be continued.
Just a question:
why again?
FSA enable automation
Goddard
(2024)
Acknowledgement
Acknowledgement:
This script is inspired by Goddard (2024).
