commit d1096a7c167dbdf6942afcaa75de699e07839eb3
parent b83ab022ca9f9e4bc57601ef55be168698940278
Author: AndrewLockVI <andrew@laack.co>
Date: Sun, 9 Feb 2025 00:11:01 -0600
Updated notes for ToC
Diffstat:
2 files changed, 6 insertions(+), 9 deletions(-)
diff --git a/docs/DeterministicFiniteAutomata.md b/docs/DeterministicFiniteAutomata.md
@@ -4,8 +4,6 @@
**Lecture:** 2
-
-
**Definition:** A deterministic finite automaton is a 5-tuple (Q, Sigma, delta, q_0, F) where each coordinate represents the following:
1. Q - Finite **set** of states.
diff --git a/docs/NonDeterministicFiniteAutomata.md b/docs/NonDeterministicFiniteAutomata.md
@@ -4,18 +4,17 @@
**Lecture:** 3
-
-
-**Definition:** An NFA is a machine that may have several choices for the next state at any point. This is to say some edges may have multiple labels.
-
-NOTE:
-
-Differences:
+**Definition:** A NFAs differ from DFAs in the following ways:
1. DFA must have transitions for each symbol whereas a NFA might not.
2. It is possible for a NFA to have a state transition with a label of epsilon, indicating such a transition has no impact upon the current word.
3. An NFA may have a state with multiple transitions for the same symbol.
+
+---
+
+As we can see, an all DFAs can be considered NFSs, but the opposite is not true.
+
When evaluating a NFA, if the machine runs into a split where it can either take one option or the other option, it creates a split (copy) and runs both in parallel. If the next input symbol does not appear on any of the arrows exiting the state occupied by the copy, the copy dies.
A good way to think of NFAs is as a tree.
