date: 2024-10-03
title: 03-TOC-Finite Automata
status: DONE
author:
- AllenYGY
tags:
- NOTE
- Compiler
- TOC
- Automata
publish: True
TOC Finite Automata
The computation power of this model is rather weak. Because it can only use a limited (finite) memory. But it is also useful in some applications.
A deterministic finite automata (DFA) is a 5-tuple
The transition function
The table has
The value in each entry is a state.
The input of a DFA is a string in the language
The output of a DFA is only accept or reject.
Suppose
Each
Each
The sequence of transitions can also be expressed as:
Remember, a DFA can be represented as a state graph. The features of the graph are listed:
Example
Let
0 | 1 | |
---|---|---|
If
For example:
A language is regular if it is recognized by some DFA (Deterministic Finite Automaton).
An NFA (Nondeterministic Finite Automaton) is a 5-tuple
Suppose
If
But if
Please pay attention to the quantifiers.
The difference between a DFA and an NFA is the transition function
This difference allows:
Automatas can be further upgraded by a special transition.
An
Such automata is defined.
An NFA with ε-moves is the same as an NFA (without ε-moves) except the transition function:
Later, we will see that ε-moves allow us to recursively construct NFAs, which is... elegant.
Let
Note: A computation model is a set of all machines of the same type.
DFA, NFA, and NFA with
For convenience, we denote the ordering on the power by
Next, we only need to show
It seems the content repeats the explanation for converting
The Intuition of the Proof:
Let
The
Let
This means the
Let
This describes all the states reachable by:
NOTE:
Let
States (
Transition Function (
Start State (
Final States (
Ensures
Uses the power set of
Algorithm Convert NFAε to DFA
Input: An NFAε N=(Q,Σ,δ,q0,F)
Output: A DFA D=(Q′,Σ,δ′,q0′,F′)
Q′←{E(q0)}, E(q0) is unmarked, and δ′←∅
while there exists an unmarked state R∈Q′ do
Mark R
for each symbol a∈Σ do
U←E(δ(R,a))
if U∈/Q′ then
Add U to Q′
end if
Add δ′(R,a)=U to δ′
end for
end while
q0′←E(q0)
F′←{R∣R has a final state in F}
return D←(Q′,Σ,δ′,q0′,F′)
Let’s try to convert this
Suppose the unmarked states are red.
Rename the states to make the DFA more readable and beautiful: