commit 699dd540edccc6ab72db5f1f2d205c1ad17815bf
parent d83820ba80452af68197128584d2f65ca7a732bc
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date: Thu, 30 Jan 2025 06:14:55 -0600
Took some notes
Diffstat:
6 files changed, 152 insertions(+), 26 deletions(-)
diff --git a/definitions/DeterministicFiniteAutomata.md b/definitions/DeterministicFiniteAutomata.md
@@ -1,4 +1,4 @@
-# Deterministic Finite Automaton (DFA)
+# Deterministic Finite Automaton (DFA)
**Source:** Theory of Computation
@@ -12,10 +12,16 @@
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)
+5. F - Set of final state(s) (F is a subset of Q)
+
+Note: A DFA **must** contain state transitions for each member of the alphabet for each state.
### 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.
+
+### Language
+
+The language of a DFA is the set of all strings that M, defined as the machine, accepts. For M to accept a word there must be a sequence of states transitions that ends in an accepting state and starts at the initial state. We say L is the language of M and can state L = L(M).
diff --git a/definitions/FiniteStateAutomata.md b/definitions/FiniteStateAutomata.md
@@ -1,9 +0,0 @@
-# Finite State Automata (FA)
-
-**Source:** Theory Of Computation
-
-**Lecture:** 2
-
-## Notes
-
-**Definition:** A finite state machine is a five tuple
diff --git a/definitions/RegularExpressions.md b/definitions/RegularExpressions.md
@@ -1,9 +0,0 @@
-# Regular Expressions
-
-**Source:** ToC Lecture
-
-**Lecture:** 1
-
-## Notes
-
-**Definition:**
diff --git a/definitions/TheoryOfComputation.md b/definitions/TheoryOfComputation.md
@@ -4,17 +4,16 @@
### Math 421 (Course Resources)
-Lecture 01/22
-
-- [FiniteStateAutomata](FiniteStateAutomata.md)
-- [RegularExpressions](RegularExpressions.md)
-
Lecture 01/24
- [Language](Language.md)
-From (Later) Lecture Slides
+Lecture 01/27
- [RegularLanguages](RegularLanguages.md)
- [DeterministicFiniteAutomata](DeterministicFiniteAutomata.md)
+
+Lecture 01/28
+
+- [DeterministicFiniteAutomata](DeterministicFiniteAutomata.md)
- [NonDeterministicFiniteAutomata](NonDeterministicFiniteAutomata.md)
diff --git a/work/linear-algebra/01-23-2025.md b/work/linear-algebra/01-23-2025.md
@@ -0,0 +1,99 @@
+how do I get the inverse of AB?
+
+A A^-1 = I = A^-1 A
+
+Let's assume A and B are both invertible.
+
+(AB) (AB)^-1 = I
+
+(AB)^-1 = B^-1 A^-1
+
+(AB)(B^-1 A^-1) = I
+
+---
+
+A A^-1 = I
+
+we use the knowledge that I = I^T to find this and then apply the same distribution from above in inversion for multiplied matricies
+this is useful because if we know A^-1 then we can also find (A^-1)^T without doing too much more work.
+
+(A^-1)^T A^T = I
+
+---
+
+A = [2 1]
+ [8 7]
+
+E_2,1 = [ 1 0]
+ [-4 1]
+
+Elementary matrix to clear 2,1
+
+(u)
+E_2,1 A = [2 1]
+ [0 3]
+
+A = L u
+
+we see L must be the inversion of E_2,1
+
+// inversion of E_2,1
+L = [1 0]
+ [4 1]
+
+A = Lu
+
+// original
+A = [2 1]
+ [8 7]
+
+// lower triangular
+L = [1 0]
+ [4 1]
+
+// upper triangular
+u = [2 1]
+ [0 3]
+
+we can also define another matrix that makes the diagonals nice and 1, but that is likely not necessary... likely.
+
+---
+
+assume A is 3x3
+
+the steps to get a reduced form is to get a 0 in 2,1
+then next we do 3,1
+the last one is to get 3,2
+
+this will give us u (upper traingular)
+this process assumes there are no 0's in places we don't want them to be otherwise
+row changes are an order. This also assumes linear independence.
+
+based on the elimination matrix above, defined as E which is the combination of all eliminations,
+we can then invert this to find L because AE = u ... so if we get the inverse and multiply both
+sides we have A = E^-1u and thus A = Lu.
+
+one thing I forgot to mention above, we don't necessarily need to combine the matricies. given that AB^-1 = B^-1 A^-1 we can
+flip the order of our transformations, take each of there inverses, and then we have L. why would we do this?
+we do this because it is easier to compute the inverses of these simple matricies.
+
+A = Lu
+
+---
+
+why does AB^-1 = B^-1 A^-1?
+
+if we assume it true we have
+
+(AB)^-1 B^-1 A^-1 = I
+
+we can then replace the first portion with:
+
+B^-1 (A^-1 B^-1) A^-1 = I
+
+B^-1 I A^-1 = I
+
+B^-1 A^-1 = I
+
+sick, although it might be bad form to be stating something is true then showing it is so. Not sure about that as a proof
+technique, but this is still pretty cool.
diff --git a/work/linear-algebra/01-24-2025.md b/work/linear-algebra/01-24-2025.md
@@ -0,0 +1,40 @@
+A = LU
+
+The multipliers go into L.
+
+---
+
+This is pretty much Gaussian elimination but with augmented matrices.
+
+---
+
+How expensive is elimination?
+
+Let's consider 3x3.
+
+There are at most, assuming no row reordering, 3 operations.
+
+This does not scale linearly though because each time we add one more row we add n-1 to the total number of computations where n is the number of columns (or rows as the matrix is assumed to be square).
+
+R(n) = R(n-1) + (n-1)
+
+n-1 + n-2 + n-3 + ... + 0
+
+duh...
+
+this can be stated as:
+
+
+this assumes it is one operation to multiply a row and then subtract. If we don't, which we may not want to, then we would find another factor of 2n added to our asymptotic function because we need to compute the multiplied row and then subtract all of the elements from that row to the other row.
+
+**_ R(n) = (n(n-1)) / 2 _**
+
+3(3 - 1) / 2 = 6 / 2 = 3
+
+---
+
+This scales as a factor of n^2 because each element adds itself.
+
+---
+
+this is kinda wrong; the issue with this is the assumption that we can do one operation to zero everything except the indices we don't want zeroed which would really never happen.
