Midnight Mathematics

Structure of grammar L is a language over an alphabet A then a grammar for L α → β α = strings of symbols taken from language A β = strings of symbols from a grammar disjoint from A. Can be interpreted as: replace α by β α produces β α rewrites β α reduces β --- Start symbol S → β Ex. Let A = { a, b, c }. S → Λ | aS | bS | cS Ex. Set of binary numerals that represent odd numbers O → B 1  B → Λ | B 0 | B 1. --- S  →  AB A  →  Λ |  aA B  →  Λ |  bB. Leftmost derivation S  ⇒  AB  ⇒  aAB   ⇒  aaAB   ⇒  aaB   ⇒  aabB   ⇒  aab . Rightmost Derivation S  ⇒  AB  ⇒  AbB   ⇒  Ab  ⇒  aAb   ⇒  aaAb   ⇒  aab . --- The Language of a Grammar (3.3.4) If G is a grammar with the start symbol S and the set of terminals T , then the language of G is the set L ( G ) = { s | s ∈ T * and S ⇒ + s }. Three simple grammars 1. {Λ, a, aa , …, a n , … } = { a n | n ∈ N}. • S → Λ | aS . 2. {Λ, ab, aabb , …, a n b n , … } = { a n b n

Inductively Defined Sets Steps needed to define a set inductively 1. There is a starting element 2. There is a construction operation to build new elements from existing elements 3. There is a statement that no other elements are in the set. Basis: Specify one or more elements of S Induction: Give one or more rules to construct new elements of S from existing elements of S Closure: State that S consists exactly of the elements obtained by the basis and induction steps. (usually assumed, not states explicitly) Note: The basis elements and the induction rules are called  constructors . Example.  Find an inductive definition for  S  = {3, 16, 29, 42, …}. Solution :   Basis : 3  Î   S . Induction : If  x   Î   S  then  x  + 13  Î   S . Recursive Functions and Procedures Constructing a Recursively Defined Procedure [or function P(x) =  f(x)] If S is an inductively defined set, we can construct a procedure P to process the elements of S as follows: 1. For each

Function (mapping, transformation, operator) Parts of a function Examples of functions floor ceiling gcd mod log What are f, A and B in the expression f : A -> B Range of a function What is the inverse of the function   f(x) = y  "f maps x to y"

Describe Basic Properties of Graphs and Trees Construct Spanning Trees for Graphs Graph Directed Graph Undirected Graphs Subgraph of a graph Path Length of a path Cycle Weighted Graph Depth-First Search Breadth-First Search Tree Node Level of node Binary tree Binary Search tree Parse Trees Spanning tree for a weighted graph Prim's Algorithm Kruskal's Algorithm

Basic Properties of: Tuples What are the two characteristics of a tuple? Product rule to count tuples Cartesian product A x  B Lists Difference from tuples Strings Languages Relations Language What is the product LM of two languages L and M? If A is an alphabet, what is A*? What is a relation, binary relation --- Regular Expression

Basic properties of sets Two characteristics of a set There are no repeated occurrences of elements There is no particular order or arrangement of the elements How do you show A is a subset of B? If A and B are sets and every element of A is also an element of B, then A is a subset of B. How do you show A = B? A is a subset of B, and B is a subset of A Operations on sets Union - A union B = set of x s.t. x is an element of A or x is an element of B Intersection - A intersect B = set of x s.t. x is an element of A and x is an element of B  Complement Cardinality Inclusion-Exclusion principle | A ∪ B | = | A | + | B | − | A ∩ B |. Inclusion-Exclusion for 3 sets | A ∪ B ∪ C | = | A | + | B | + | C | − | B ∩ C | − | A ∩ B | − | A ∩ C | + | A ∩ B ∩ C | Difference rule | A − B | = | A | − | A ∩ B |.