commit 36e793522bf660ed9cf866014d26b309a32fc594
parent fc7bf0a27e989465d971c0fe1485f8edfc5627bb
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date: Fri, 17 Jan 2025 17:52:07 -0600
Took first day of notes for semester on automata.
Diffstat:
7 files changed, 84 insertions(+), 0 deletions(-)
diff --git a/DeterministicFiniteAutomata.md b/DeterministicFiniteAutomata.md
@@ -0,0 +1,21 @@
+# Deterministic Finite Automaton (DFA)
+
+**Source:** Theory of Computation
+
+**Lecture:** 2
+
+## Notes
+
+**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.
+2. Sigma - Finite [Alphabet](Alphabet.md).
+3. delta - This is a function from Q x Sigma -> Q. As such, this represents state transitions, referred to as the transition function.
+4. q_0 - Initial state (q_0 \in Q)
+5. F - Set of final states (F is a subset of Q)
+
+### Representation
+
+Often these are represented as a directed labeled graph (transition diagram).
+
+When creating these accepting states (final states) have a concentric circle in their node (double circles as prof. referred to it) and the start state (only 1) has an arrow leading in from nowhere.
diff --git a/FiniteStateAutomata.md b/FiniteStateAutomata.md
@@ -0,0 +1,9 @@
+# Finite State Automata (FA)
+
+**Source:** Theory Of Computation
+
+**Lecture:** 2
+
+## Notes
+
+**Definition:**
diff --git a/NonDeterministicFiniteAutomata.md b/NonDeterministicFiniteAutomata.md
@@ -0,0 +1,17 @@
+# Non-deterministic Finite Automata (NFA)
+
+**Source:** Theory of Computation
+
+**Lecture:** 3
+
+## Notes
+
+**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:
+
+Non-determinism is a generalization of determinism so every DFA is a NFA, but not necessarily the other direction, hence the statement above 'some edges may have'.
+
+Additionally, it is also 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.
+
+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.
diff --git a/RegularExpressions.md b/RegularExpressions.md
@@ -0,0 +1,9 @@
+# Regular Expressions
+
+**Source:**
+
+**Chapter:**
+
+## Notes
+
+**Definition:**
diff --git a/RegularLanguages.md b/RegularLanguages.md
@@ -0,0 +1,9 @@
+# Regular Languages
+
+**Source:** Theory of Computation
+
+**Lecture:** 1
+
+## Notes
+
+**Definition:** A language is a regular language if there exists a finite automaton that recognizes it (ie. the FA's language is the language in question).
diff --git a/TheoryOfComputation.md b/TheoryOfComputation.md
@@ -0,0 +1,18 @@
+# Theory of Computation
+
+## Links By Resource
+
+### Math 421 (Course Resources)
+
+- AutomataTheory
+ - [FiniteStateAutomata](FiniteStateAutomata.md)
+ - [DeterministicFiniteAutomata](DeterministicFiniteAutomata.md)
+ - [RegularExpressions](RegularExpressions.md)
+ - [RegularLanguages](RegularLanguages.md)
+ - [NonDeterministicFiniteAutomata](NonDeterministicFiniteAutomata.md)
+ - ContextFreeGrammars
+ - Alphabet
+ - PushdownAutomata
+ - TuringMachines
+- ComputabilityTheory
+- ComplexityTheory
diff --git a/index.md b/index.md
@@ -13,6 +13,7 @@ This is the index for my main note classifications. I will maintain this as a ho
- [DiscreteMath](DiscreteMath.md)
- [Assembly](Assembly.md)
- [ComputerSecurity](ComputerSecurity.md)
+- [TheoryOfComputation](TheoryOfComputation.md)
## Other Focuses
