Personal final notes for CSE 105 Theory of Computability. Not comprehensive – only like a final exam cheat sheet. Regular Expression Precedence: \((R)\) → \(R^{*}\) → \(R_{1} R_{2}\) → \(R_{1} \cup R_{2}\) \(\emptyset\) represents empty set; \(\epsilon\) represents empty string; \(R^+ \equiv RR^*\) Proving closure Given: What does it mean for L to be in class? e.g. \(L\)* a regular language, so given a DFA/NFA* \(M_L\) WTS: The result of applying the operation to \(L\) is still in this class.
Notes
Differential Equations Classification Ordinary/Partial involving only ordinary derivatives with respect to a single independent variable is called an ordinary differential equation. involving partial derivatives with respect to more than one independent variable is a partial differential equation. Linear/Non-linear Linear: One in which the dependent variable \(y\) and its derivatives appear in additive combinations of their first powers. May be written in the form \[ a_{n}(x) \frac{d^{n} y}{d x^{n}}+a_{n-1}(x) \frac{d^{n-1} y}{d x^{n-1}}+\ldots+a_{1}(x) \frac{d y}{d x}+a_{0}(x) y=F(x) \]
Personal notes for CSE20 - Discrete Mathematics for Computer Science. Taken Fall 2020, with professor Shachar Lovett. See Course Homepage Sets Recursive definition of sets Basis step: Specify finitely many elements of \(S\) Recursive step: Give a rule for creating a new element of \(S\) from known values existing in \(S\), and potentially other values. String The set \(\Sigma^*\)of strings over the alphabet \(\Sigma\) is defined recursively by Basis step: \(\lambda \in \Sigma^*\) (where \(\lambda\) is the empty string containing no symbols)