Formal Languages Mathematical Preliminaries PDF

Formal Languages Mathematical Preliminaries Charbel Boustany Msc Systems Engineering IEEE Member AUST Zahle  Mathematical Preliminaries Sets Functions Relations Graphs Proof Techniques 2  SETS A set is a collection of ele...

Formal Languages Mathematical Preliminaries Charbel Boustany Msc Systems Engineering IEEE Member AUST Zahle  Mathematical Preliminaries Sets Functions Relations Graphs Proof Techniques 2  SETS A set is a collection of elements A {1, 2,3} B {train,bus,bicycle, airplane } We write 1 A shipB 3  Set Representations C = { a, b, c, d, e, f, g, h, i, j, k } C = { a, b, …, k } finite set S = { 2, 4, 6, … } infinite set S = { j : j > 0, and j = 2k for some k>0 } S = { j : j is nonnegative and even } 4 A = { 1, 2, 3, 4, 5 } U 6 A 2 3 8 1 7 4 5 9 10 Universal Set: all possible elements U = { 1 , … , 10 } 5  Set Operations A = { 1, 2, 3 } B = { 2, 3, 4, 5} A B Union 2 4 1 A U B = { 1, 2, 3, 4, 5 } 3 5 Intersection U A B = { 2, 3 } 2 3 Difference A-B={1} 1 B - A = { 4, 5 } Venn diagrams 6  Complement Universal set = {1, …, 7} A = { 1, 2, 3 } A = { 4, 5, 6, 7} 4 A A 3 6 1 2 5 7 A=A 7 { even integers } = { odd integers } Integers 1 odd even 6 5 2 0 4 3 7 8 DeMorgan’s Laws AUB=A B U A B=AUB U 9  Empty, Null Set: ={} SU =S S = U = Universal Set S- =S -S= 10  Subset A = { 1, 2, 3} B = { 1, 2, 3, 4, 5 } A B U Proper Subset: A B U B A 11  Disjoint Sets A = { 1, 2, 3 } B = { 5, 6} A B= U A B 12  Set Cardinality For finite sets A = { 2, 5, 7 } |A| = 3 (set size) 13  Powersets A powerset is a set of sets S = { a, b, c } Powerset of S = the set of all the subsets of S 2S = { , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} } Observation: | 2S | = 2|S| ( 8 = 23 ) 14  Cartesian Product A = { 2, 4 } B = { 2, 3, 5 } A X B = { (2, 2), (2, 3), (2, 5), ( 4, 2), (4, 3), (4, 5) } |A X B| = |A| |B| Generalizes to more than two sets AXBX…XZ 15  FUNCTIONS domain range 4 A B f(1) = a a 1 2 b 3 c 5 f : A -> B If A = domain then f is a total function otherwise f is a partial function 16  RELATIONS R = {(x1, y1), (x2, y2), (x3, y3), …} xi R yi e. g. if R = ‘>’: 2 > 1, 3 > 2, 3 > 1 17  Equivalence Relations Reflexive: xRx Symmetric: xRy yRx Transitive: x R y and y R z xRz Example: R = ‘=‘ x=x x=y y=x x = y and y = z x=z 18  Equivalence Classes For equivalence relation R equivalence class of x = {y : x R y} Example: R = { (1, 1), (2, 2), (1, 2), (2, 1), (3, 3), (4, 4), (3, 4), (4, 3) } Equivalence class of 1 = {1, 2} Equivalence class of 3 = {3, 4} 19  GRAPHS A directed graph e b node a d c Nodes (Vertices) V = { a, b, c, d, e } Edges E = { (a,b), (b,c), (b,e),(c,a), (c,e), (d,c), (e,b), (e,d) 20 }  Labeled Graph 2 6 e b 2 1 3 a 6 d 5 c 21  Walk e b a d c Walk is a sequence of adjacent edges (e, d), (d, c), (c, a) 22  Path e b a d c Path is a walk where no edge is repeated Simple path: no node is repeated 23  Cycle base e b 3 a 1 d 2 c Cycle: a walk from a node (base) to itself Simple cycle: only the base node is repeated 24  Euler Tour 8 base 7 e b 1 4 6 a 5 2 d 3 c A cycle that contains each edge once 25  Hamiltonian Cycle 5 base e b 1 4 a 2 d 3 c A simple cycle that contains all nodes 26 Finding All Simple Paths e b a d c origin 27  Step 1 e b a d c origin (c, a) (c, e) 28  Step 2 e b a d (c, a) c origin (c, a), (a, b) (c, e) (c, e), (e, b) (c, e), (e, d) 29  Step 3 e b a d (c, a) c origin (c, a), (a, b) (c, a), (a, b), (b, e) (c, e) (c, e), (e, b) (c, e), (e, d) 30  Step 4 e b a d (c, a) (c, a), (a, b) c origin (c, a), (a, b), (b, e) (c, a), (a, b), (b, e), (e,d) (c, e) (c, e), (e, b) (c, e), (e, d) 31  Trees root parent leaf child Trees have no cycles 32  root Level 0 Level 1 leaf Height 3 Level 2 Level 3 33 Binary Trees 34  PROOF TECHNIQUES Proof by induction Proof by contradiction 35  Induction We have statements P1, P2, P3, … If we know for some b that P1, P2, …, Pb are true for any k >= b that P1, P2, …, Pk imply Pk+1 Then Every Pi is true 36  Proof by Induction Inductive basis Find P1, P2, …, Pb which are true Inductive hypothesis Let’s assume P1, P2, …, Pk are true, for any k >= b Inductive step Show that Pk+1 is true 37  Example Theorem: A binary tree of height n has at most 2n leaves. Proof by induction: let L(i) be the maximum number of leaves of any subtree at height i 38 We want to show: L(i)