Sets and Relations PDF

ELEMENTS well defined objects SETS collection of well defined objects represented by a CAPITAL letter METHOD OF SET NOTATION ROSTER/TABULAR/LIST METHOD o represented by actually listing the elements o separated by comma and enclosed between curly...

ELEMENTS well defined objects SETS collection of well defined objects represented by a CAPITAL letter METHOD OF SET NOTATION ROSTER/TABULAR/LIST METHOD o represented by actually listing the elements o separated by comma and enclosed between curly brackets { }. ▪ Set of even numbers less than 10: {2, 4, 6, 8} SET BUILDER / RULE METHOD o sometimes defined by stating property (P) which characterizes all the elements in the set o elements must satisfy the given rule of the set ▪ A = { x | x is an even number, x < 10 } Venn Diagram o represents relation and operator using the plane geometrical figures (rectangle, circle, ellipse) TYPES OF SETS FINITE SET o set with countable elements ▪ {1,2,3} INFINITE SET o set with uncountable elements ▪ {-∞,+∞} EMPTY SET o set with no element o aka. null or void set ▪ {}  UNIT SET o set with only one element o aka. singleton ▪ {1} SUBSET o each element of set A is also an element of set B ▪ SET A : {1,2,3} ▪ SET B : {1,2,3,4,5,6} A ⊆ B (A is a subset of B) o No. of subsets formula : 2^n ▪ SET A : (2)(2)(2) = 8 ▪ SET B : (2)(2)(2)(2) = 16 PROPER SUBSET o at least one element in B is not contained in A ▪ SET A : {1,2,3} ▪ SET B : {1,2,3,4} A ⊂ B (A is a proper subset of B) o No. of proper subsets formula : 2^n - 1 ▪ SET A : 7 ▪ SET B : 15 FAMILY SET o class of sets or the set of sets ▪ Set A = { {1, 2, n}, {1, n}, {2, n}, {1, 1, n}, {2, 2, n}, {1, 2, m, k} } POWER SET o set of all subsets of a given set o denoted by P(A) o Set A = {apple, banana} ▪ P(A) = { {}, {apple}, {banana}, {apple, banana} } UNIVERSAL SET o set that contains all objects, including itself o the general set ▪ U = {0,1,2,3,4,5} COMPLEMENT o “Ac is the set containing everything that is not in A” ▪ U = {0,1,2,3,4,5} ▪ A = {2,4,5} ▪ Ac = {0,1,3}  “Standard” Sets o ℕ - non-negative integers o ℤ - {x | x is an integer,(-∞,+∞)} o ℚ - numbers that can be expressed as fraction o ℝ - (-∞,+∞) CARDINALITY number of elements in a set SET RELATIONS EQUAL SETS o same elements and same cardinality EQUIVALENT SETS o same cardinality DISJOINT SET o no common elements, different cardinalities SET OPERATIONS UNION o contains all the elements of the sets involved INTERSECTION o set that contains exactly the common elements of the sets involved. SET DIFFERENCE set that contains everything that is in the minuend but not in subtrahend o Minuend - Subtrahend = Difference ▪ A = {1,3,9} ▪ B= {3,5} ▪ A-B = {1,9} RELATIONS a relationship between elements of two sets  A={1,2,3} o Reflexive Relation ▪ every element is related to itself R={(1,1),(2,2),(3,3),(1,2),(2,3)} o Symmetric Relation ▪ any element pair is related to each other R={(1,2),(2,1),(2,3),(3,2)}. o Transitive Relation ▪ one element is related to a second, and the second is related to a third, then the first element is also related to the third R={(1,2),(2,3),(1,3)}. o Equivalent Relation ▪ a relation that is reflexive, symmetric, and transitive R={(1,1),(2,2),(3,3),(4,4),(1,3),(3,1),(2,4),(4,2)} FUNCTIONS o a way of matching members from set “A” to set “B” o set A should be associated with exactly one element, but B can have more or less than 1 o Every function is a relation, but not all relations are functions. ▪ Injective Function one to one relationship ▪ Surjective Function each element of B have a pair ▪ Bijective Function both injective and surjective ▪ Inclusion Function domain is a subset of its codomain GRAPH bunch of vertices (Nodes) represented by circles connected by edges represented by lines a connected tree that has no simple cycle TREES Undirected graphs any two vertices are connected by exactly one simple path does not contain a cycle ADJACENT VERTICES pair of vertices that determine an edge are “adjacent” vertices CIRCUIT path that begins and ends at the same vertex SIMPLE PATH no vertex appears more than once in the vertex sequence CONNECTED GRAPH there is a path from any vertex to any other vertex in the graph DISCONNECTED GRAPH there is no path from any vertex to any other vertex in the graph o COMPONENT ▪ occurs only to disconnected graph ▪ connected pieces of the graph SIMPLE CYCLE one that does not repeat any node except for the first and las MODULE 2 AUTOMATA THEORY (Theory of Computation) theoretical branch of computer science roots established during 20th century pure mathematics of computer science theory of what can and cannot be computed HISTORY OF AUTOMATA 1936 : First Infinite Model by Alan Turing 1943 : First description of finite automata by Warren McCulloch and Walter Pitts 1955 : Generalized Automata Theory for Machines by G.H. Mealy and E.F. Moore ALPHABET finite, nonempty, set of symbols denoted by Σ o Σ+ ▪ set of all nonempty string on Σ ▪ Σ = Σ+ union {lambda}* STRING list of symbols from an alphabet Length of a string number of positions for symbols in the string Lexicographic ordering same as dictionary ordering (alphabetical) shorter precedes longer Language a set of strings from the same alphabet State its purpose is to remember the relevant portion of the system’s history Finite Automate a state diagram that comprehensively captures all the possible states and transitions that a machine can take as response to inputs recognizer for “Regular Languages” Deterministic Finite Automaton (DFA)  automaton cant be in more than one state at any one time does not accept empty strigs Nondeterministic Finite Automaton (NFA) automaton may be in several states at once allows zero, or more for every inputs a finite automaton where there exit a non-determinism for a given input symbol State Diagram (Transition Graph) directed graph where vertices represent the internal state of the automaton, and the edges represent the transitions Dead State non-final state which transits itself for all input symbol Regular Expression simple expression that descripts the languages accepted by a FA very intuitive useful in a variety of contexts sequence of characters that forms a search pattern, mainly for use in pattern matching with strings or string matching Regular set set accepted by a finite automaton Closure set is closed under an operation if, whenever the operation is applied to members of the set, the result is also a member of the set. OPERATORS OF REGULAR EXPRESSION Union o set of string that are in either L1 or L2, or both  Concatenation o set of strings formed by taking any string and concatenating it with any string Kleene Closure(*) o set of strings that can be formed by taking any number of strings, including the null string Positive Closure(+) o set of strings that can be formed by taking any number of strings, excluding the null string Moore Machines its output depends only on present state considered as “counting machine” has 6 tuples o Q ▪ set of states o q0 ▪ initial states o Σ ▪ inputs o O ▪ outputs o δ ▪ state transitions o λ ▪ output function (transitions) Mealy Machine its output depends only on present state and current input symbol considered as “output producer” Noam Chomsky gave a mathematical model of Grammar which is effective for writing computer languages Context Free Grammar (CFG) also known as Backus-Naur Form (BNF) has 4 tuples o V ▪ non-terminal (Capital) o T ▪ terminal (lowercase) o S ▪ start symbol o P ▪ production rules used to derive strings Derivation [of strings] generation of language using specific rule Regular Grammar Right Linear Grammar o Non-terminal symbol appears at the end of the production Left Linear Grammar o Non-terminal symbol appears at the beginning of the production Derivation Tree also known as Parse Tree ordered rooted tree that graphically represents the semantic information of strings derived from CFG o Root Vertex ▪ MUST be labelled by the start symbol o Vertex ▪ labelled by non-terminal(Capital) o Leaves ▪ labelled by terminal(lowercase) or lambda Derivation/Yield of a Tree final string obtained by concatenating the labels of the leaves of the tree from left to right, ignoring the Nulls. APPROACH TO DRAW A DERIVATION TREE Top-down Approach o starts with starting symbol then goes down to tree leaves using productions Bottom-up Approach o starts from tree leaves then proceeds upward to the root(starting symbol) o general idea is to “reduce” the input string back to the start symbol Sentential Form partial derivation tree contains the root TYPES OF DERIVATION TREE Left Derivation Tree o obtained by applying production to the leftmost variable in each step Right Derivation Tree o obtained by applying production to the rightmost variable in each step Ambiguous Grammar grammar where exists two or more derivation tree for some strings Simplification reduction of CFG elimination of production rules and symbols that are not needed for derivation of strings o Useless Productions ▪ productions which involves useless symbols o Useless Symbols ▪ variables and terminals that do not appear in any derivation of string of terminals o Reduced Grammar ▪ result of useless symbols and productions Chomsky Normal Form (CNF) a context-free grammar where every production rule is of the form: o A -> BC or A -> ▪ where A, B, and C are non-terminal symbols, and 'a' is a terminal symbol. Context-Free Language (CFL) consists of a set of rules for combining symbols to form valid strings in the language. Greibach Normal Form (GNF) For every CFL without epsilon, there exist a grammar in which every production is of the form: A → aV where A is a variable, a is exactly one terminal, V is the string of none or more variables used to construct a Pushdown Automata Pushdown Automata (PDA) a way to implement a context-free grammar in a similar way that a DFA is designed for a regular grammar can remember infinite amount of information equal to NFA with a stack o Push - new symbol added at the top o Pop - top symbol is read and removed may or may not read an input symbol, but it has to read the top of the stack in every transition Instantaneous Description represented by triplet (tuples) o q ▪ state o w ▪ unconsumed input o s ▪ stack contents Turnstile Notation used for connecting pairs of ID’s that represent one or many moves of a PDA denoted by “⊢” Parsing used to derive a string using the production rules of a grammar o Top-Down Parser ▪ starts from the top with the start-symbol o Bottom=Up Parser ▪ starts from the bottom and comes to the start symbol Turing Machine proposed by Alan M. Turing (1912-1954) a hypothetical machine in 1936 whose computations are intended to give an operational and formal definition of the intuitive notion of computability in the discrete domains mathematical model which consists of an infinite length tape divided into cells on which input is given 6 Types of Fundamental Operation Read Write Move tape left Move tape right Change state Halt