Welcome to cse103-notes’s documentation!
¶
Contents:
Introduction
Algorithmic Problems
Problem Difficulties
Sets
Notation
Russel’s Paradox
Relations
Properties
Functions
Graph
Strings
Propositional Logic
Useful Tautologies
Cardinality
Proofs
Induction
Contrapositive
Contradiction
Pidgeonhole Principle
DFA
Extended Transition Function
Thms
Examples
Two Ones
Even Ones
3 As
3 Consec As
0m0
00011
Odds/Evens
Div3
Len3
Intersection
Union
NFA
Examples
Subset Construction
Epsilon Moves
Closure
Concatenation
Kleene Star
Reversal
Regular Expressions
Kleene’s Thm
The Other Way Around
Example
Pumping Lemma
Proof
Examples
Ex 1
Ex 2
Ex 3
Ex 4
Ex 5
Ex 6
Ex 7
Ex 7b
Ex 8
Ex 9
Ex 10
Ex 11
DFAs Extra
Minimizing a DFA
Identifying Equivalent States
Equivalence Relations
Myhill-Nerode
Ex 1
Ex 2
Ex 3
Ex 4
Ex 5
Ex 6
Ex 7
Additional Comments
Two-Way DFAs
Example
Additional Comments
Context-Free Languages
Definition
Convention
Examples
Ex 1
Ex 2
Ex 3
Ex 4
Ex 5
Ex 6
Ex 7
Ex 8
Ex 9
Ex 10
Ex 11
Special Constructions
DFA Relation
Closure
Union
Concatenation
Kleene Star
Intersection (Not)
Chomsky Normal Form
Converting to CNF
Pumping Lemma for CFLs
Proof
Ex 1
Ex 2
Ex 3
Ex 4
Ex 5
Push-Down Automata
Formal Definition
Ex 1
Ex 2
Ex 3
CFGs
Ex 1
Ex 2
CKY Algorithm
Ex 1
Ex 2
Parsing
Ambiguity
Solution 1: Design
Turing Machines
Definition
Examples
Ex 1
Ex 2
Ex 3
Ex 4
Ex 5
Ex 6
Ex 7
Ex 8
Variants
Multi-Tape TM
Infinite Tape
Universal TM
Special Coding
Halting Problem
Diagonalization Review
Proof
Example
Reduction
Rice’s Theorem
Definitions
Thm
Proof
Conclusion
Indices and tables
¶
Index
Module Index
Search Page
cse103-notes
Navigation
Contents:
Introduction
Sets
Proofs
DFA
NFA
Regular Expressions
Pumping Lemma
DFAs Extra
Context-Free Languages
Push-Down Automata
Parsing
Turing Machines
Related Topics
Documentation overview
Next:
Introduction
Quick search