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.
Course
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)