What:
A model used to represent and control the execution flow in a system with a finite number of states.
Components:
- States (): The finite set of states the automaton (system) can even be in
- Alphabet (): The finite set of input symbols
- Transition Function (): A function that defines how the state changes based on inputs it’s gotten.
- Start State (): The initial state the automaton begins.
- Accept States (): A set of states that determine when an input is accepted.
Example:
Let’s say we want an automaton that accepts the string "ab"
.
- States:
{q₀, q₁, q₂}
- Alphabet:
{a, b}
- Transitions:
q₀ → a → q₁
q₁ → b → q₂
q₂
is the accepting state.
If we input "ab"
, we reach q₂
, so it’s accepted. If we input "aa"
, it gets stuck and is rejected.
It Gets Harder:
- Deterministic Finite Automaton (DFA):
- For each state and input symbol, there’s exactly one possible transition.
- There are no -transitions.
- Non-Deterministic Finite Automaton (NFA):
- A state may have multiple transitions for the same input.
- Some transitions may occur without input (-transitions)
- Probabilistic Finite Automaton (PFA):
- Each transition has a probability rather than being deterministic.
- Pushdown Automaton (PDA):
- Like an FSA, but using a stack, allowing it to handle more complex languages, e.g. context-free grammars.
Converting from Regular Expressions to DFA:
Overview:
- Convert from RE to NFA: We do this because RE has implicit non-determinism (-transition).
- Convert the NFA to DFA: We’ll be left with some left-over states after this.
- Simplify the DFA: Remove the unnecessary left-over states.
1. Convert RE to NFA
RE | Corresponding NFA |
---|---|
a | Single-state transition: q0 → a → q1 |
AB (Concatenation) | Connect final state of A to start state of B using an ε-transition. |
A|B (Union) | Use ε-transitions to branch into A or B . |
A* (Kleene Star) | Create a loop using ε-transitions to allow repetition or skipping A . |
A+ (Kleene Plus) | Similar to A* , but requires at least one occurrence of A . |
A? (Optional) | Use an ε-transition to optionally skip A . |
Example: Convert a*
to NFA
For a*
(zero or more occurrences of a
):
- Create a new start and accepting state.
- Add ε-transitions to allow:
- Skipping
"a"
(direct ε-transition from start to accept). - Repeating
"a"
by looping back to itself.
- Skipping
NFA Diagram for a*
:
(q0) --ε--> (q1) --a--> (q2) --ε--> (q1)
(q1) --ε--> (q3) (q3 is the final state)
2: Convert NFA → DFA (Subset Construction)
Subset Construction Algorithm
- Compute ε-closures:
- The ε-closure of a state is the set of all states reachable via ε-transitions.
- Define the initial DFA state as the ε-closure of the NFA’s start state.
- Process each DFA state:
- Compute transitions for each input symbol.
- The new state is the ε-closure of the set of NFA states reached.
- Mark final states:
- If any state in the DFA contains an accepting NFA state, it becomes an accepting DFA state.
- Repeat until no new states are generated.
Example: Convert NFA (for a*
) to DFA
NFA for a*
(from Step 1):
(q0) --ε--> (q1) --a--> (q2) --ε--> (q1)
(q1) --ε--> (q3) (q3 is accepting)
Subset Construction
NFA State Set | Input a | Resulting DFA State |
---|---|---|
{q0, q1, q3} | a | {q2, q1, q3} |
{q2, q1, q3} | a | {q2, q1, q3} |
Since {q1, q3}
contains the accepting state (q3
), the corresponding DFA state is also accepting.
Thus, the DFA for a*
is:
(q0) --a--> (q1)
(q1) --a--> (q1) (loops)
(q1 is accepting)
Step 3: Minimise the DFA
Once we have the DFA, we can minimise it by:
- Removing unreachable states.
- Merging equivalent states (states that behave identically).
Minimisation Algorithm
- Partition states into two groups:
- Accepting states.
- Non-accepting states.
- Refine partitions:
- Two states are equivalent if they transition to the same group for all inputs.
- Merge equivalent states.
- Construct the minimised DFA.
Example: Minimising a DFA
Consider this DFA:
(q0) --a--> (q1) --a--> (q1)
(q1) --a--> (q1)
(q1 is accepting)
Since q1
is the only useful state, the minimized DFA is simply:
(q0) --a--> (q1)
(q1) --a--> (q1) (loops)
NFA for a(b|c)*:
is the set of all w possible states reachable from , given an input .