Mathematical Preliminaries PDF

IT2005 Mathematical Preliminaries ∪ε - closure Union of null closure of... Important Notations and S...

IT2005 Mathematical Preliminaries ∪ε - closure Union of null closure of... Important Notations and Symbols for Reference (Sunitha & Kalyani, 2016) ∏k k-Equivalence class Notation/Symbol Meaning ⇒ Implies U Universal set Λ Out function a∈A a belongs to set A R Regular expression a∉A a does not belong to set A h Homomorphism function ⌀ Empty set (Phi) A⇒α A derives α on one or more substitutions ⇔ If and only if Γ Stack symbol |A| Cardinality of A Z0 Initial stack symbol A⊆B A is a subset of set B γ The content of the stack read from top to bottom A⊂B A is a proper subset of set B B Blank symbol on the tape ℘ (A) Power set of A Instantaneous description of Turing Machine A∪B Union of sets A and B # Special tape symbol A∩B Intersection of sets A and B ⊘, $ Special tape-end marker in Linear-bound Automata A−B Complement of B in A/ Difference operation ∀ For all values of A´ Complement of A ⅂ Negation or NOT < a, b > Ordered pair A×B Cartesian product ˄ Conjunction or AND aRb or Rab a is related to b under the relation R ˅ Disjunction or OR R´ Complement of relation → Implication or IF-THEN R-1 Inverse of relation R ↔ Biconditional F (x) Image of x under f ∃ There exists F: A→B Function from A to B GOF Composition of F and G Set Theory idA or IA Identity function on A Sets – These are used to describe a collection of objects. ∑ Alphabet set Elements – These are the objects within a set. ∑* Set of all strings over an alphabet ∑ Subset – This is a set that contains elements that can all be found in another defined set or a universal set. Furthermore, a set C is a subset of a set D if ∑+ Set of all strings over a non-empty alphabet ∑ every element of C is also an element of D. ε Empty string (Epsilon) Power Set – This is the set of all subsets of a defined set. (V, T, P, S) A grammar Empty Set – It is a set having no elements in it. α String of terminals and non-terminals Finite Set – A set that contains no element or a finite number of elements. ∆ Transition function or set of output symbols Infinite Set – A set that contains an infinite number of elements. Q Set of states Three (3) Methods to Describe Sets (Sunitha & Kalyani, 2016) F Set of final states 1. List notation – This method is suitable only for finite sets. It is done by ∈ Belongs to listing all its elements. Ex. {1, 2, 4, 24, 37} 01 Handout 1 *Property of STI  [email protected] Page 1 of 3  IT2005 2. Predicate notation – This method is done by stating a shared property or Two (2) Representations of Relation (Sunitha & Kalyani, 2016) condition that holds for all the elements in the set. Ex. {x|x is a letter of the 1. Relation represented as a matrix. English alphabet} Ex. Set A = {2, 4, 6} has m elements and set B = {a, b} has n elements. 3. Recursive rule – This method is made by defining a set of rules that The relation matrix M can be defined as m×n. If there is a relation R generate or define its elements. Ex. Set C of even numbers greater than between sets A and B defined as ordered pairs (2, a) (4, a) (6, b), then 3: a) 4 ∈ C; b) if x ∈ C, then x+2 ∈ C; Nothing else belongs to C. the relation matrix M can be represented as: Set Operations (Kandar, 2013) Union: If there are two (2) sets C and D, then their union is denoted by C∪D. In general, A ∪ B = {x | x ∈ A or x ∈ B}. Intersection: If there are two (2) sets C and D, then their intersection is denoted by C∩D. In general, A ∩ B = {x | x ∈ A and x ∈ B}. Difference: If there are two (2) sets C and D, then their difference is denoted by C−D. In general, A − B = {x | x ∈ A and x ∉ B}. 2. Relation represented as a graph. Complement: The complement of a set, which is a subset of a larger set Ex. Set A = {p, q, r} with a defined relation R = {(p,p), (q,p), (q,r)}. If a set U is denoted by C´. In general, A′ = {x ∈ U: x ∉ A}. has n number of elements, then the graph will have n number of nodes. Cartesian Product: If there are two (2) sets C and D, then their Cartesian The edges in the graph indicate the relation R. Then, the relation graph is product is denoted by C × D. In general, A×B = {(a, b) | a ∈ A and b ∈ B}. given as: Concatenation: If there are two (2) sets C and D, then their concatenation is denoted by C·D. In general, A·B = {ab | a is in A, and b is in B}. Relations Relations – These are links existing between objects; therefore, it pertains to relationships between elements of sets. Figure 1. A relation represented as a graph. Binary Relation: If A and B are any sets R ⊆ A × B, R is called a binary relation Properties of Relation (Sunitha & Kalyani, 2016; Kandar, 2013) from A to B or a binary relation between A and B. The relation R ⊆ A × A is Reflexive – A relation on A is said to be reflexive if, for each a ∈ A, a is called a relation in or on A. related to a. If we let R denote the relation, then we have aRa for each a Domain Relation: The domain refers to a set of values for which a specific ∈ A. In general, the relation is said to be reflexive, if (a, a) ∈ R, for every a function is defined (Varsity Tutors, n.d.). The set domain R = { a | ∈ R ∈ A. for some b} is called the domain of the relation R. Irreflexive – A relation on A is said to be irreflexive if, for each a ∈ A, a is Range Relation: The range refers to the set of values that a specific function not related to a. This is not the negation of the definition of reflexive. takes (Varsity Tutors, n.d.). The range R = { b | ∈ R for some a} is called Symmetric – A relation R on A is symmetric if aRb implies bRa is true. the range of the relation R. Antisymmetric – A relation R on A is antisymmetric if aRb implies bRa is false. Transitive – A relation R is said to be transitive for a, b, c ∈ A if aRb and bRc are true, then aRc is also true. Equivalence Relation – A relation R is said to be an equivalence relation on a set if R is reflexive, symmetric, and transitive. 01 Handout 1 *Property of STI  [email protected] Page 2 of 3  IT2005 Functions Function – It may refer to a specific process or as correspondence. It is generally represented in set-theoretic terms as a specific kind of relation. The characteristic property of a function is that it relates exactly one output to each of its admissible inputs (Sunitha & Kalyani, 2016). Types of Function (Sunitha & Kalyani, 2016) 1. One-to-one Function – There is a one-to-one correspondence between the elements of two different sets. Figure 4. An onto function. 4. Into Function – This function has at least one (1) element of set B that has no corresponding element from set A. Figure 2. A one-to-one function. 2. Many-to-one Function – There is a many-to-one correspondence between the elements of two different sets. Figure 5. A into function. References: Kandar, S. (2013). Introduction to Automata Theory , Formal Languages and Computation. Dorling Kindersley (India) Pvt. Ltd. Sunitha, K. & Kalyani, N. (2016). Formal Language and Automata Theory. Pearson India Education Services Pvt. Ltd. Varsity Tutors. (n.d.). Domain and Range. Retrieved from https://www.varsitytutors.com/hotmath/hotmath_help/topics/domain-and-range on May 18, 2020 Figure 3. A many-to-one function. 3. Onto Function – This function has every element of set B with at least one (1) corresponding element from set A. o Bijection – A function that is one-to-one and onto at the same time. o Surjection – A function that is many-to-one and onto at the same time. 01 Handout 1 *Property of STI  [email protected] Page 3 of 3  IT2005 Formal Languages and non-terminals, that is, no restrictions on either side of productions. Alphabet, String, Language, and Grammar Every grammar is included in it if it has at least one non-terminal on Alphabet – It refers to a finite collection of symbols denoted by ∑. the left-hand side (LHS). Examples: English alphabet ∑ = {a, b,…, z}; Binary alphabet ∑ = {0, 1}. b. Type 1 grammar - Context-sensitive grammar (CSG): This defines the context-sensitive languages. In CSGs, all the productions of the String/word – It refers to a set of symbols from an alphabet. form α → β where length of α is less than or equal to length of β (i.e. Examples: 001, 1110, and 01100 are stings from a binary alphabet; a10b, |α| ≤ |β|), α and β may have any number of terminals and non- 11ab, and ace01 are not strings from a binary alphabet. terminals. c. Type 2 grammar - Context-free grammar (CFG): This defines the A word over an alphabet can be any finite sequence, or a string, or a group context-free languages. CFGs are defined by rules of the form α → β of letters. The set of all words over an alphabet ∑ is usually denoted by with |α| ≤ |β|, where |α| = 1 and is a non-terminal, and β is a string of ∑*. For any alphabet, there is only one word with zero (0) length, the terminals and non-terminals. α can be replaced by β regardless of empty string/word, which is often denoted by an Epsilon ε, which indicates where it appears. Hence, the name context-free grammar. Context- a no input symbol (Sunitha & Kalyani, 2016). free languages define the syntax of all programming languages. d. Type 3 grammar - Regular grammar (RG): This defines the regular languages. Such grammar restricts its rules to a single non-terminal Language – This is a dynamic set of visual, auditory, or tactile symbols of on the LHS. The right-hand side (RHS) consists of either a single communication and the specific elements used in language manipulation. It terminal or string of terminals with a single non-terminal on the left or also refers to the use of systems as a general phenomenon (Sunitha & Kalyani, right end. Rules can be of the form A → a B | a or A → Ba | a. The 2016). rule S → ε is also allowed. This family of formal languages can be Grammar – It is defined as a set of 4-tuple (tuple is a finite ordered list of obtained by regular expressions. Regular languages are used to elements) V, T, P, and S, where: define search patterns and the lexical structure of programming V is a set of non-terminals (variable) languages. T is a set of terminals (primitive symbols) P is a set productions (rules) that relate the non-terminal and terminals Graph and Trees S is the start symbol with which strings in grammar are derived Graph – It is an abstract representation of a set of objects where some pairs of objects are connected by directed or undirected links. The interconnected Types of Grammars – Chomsky Hierarchy (Sunitha & Kalyani, 2016) objects are called vertices or nodes, and the links that connect some pairs of Linguist Noam Chomsky defined a hierarchy of languages, in terms of vertices are called edges or arcs. A graph G = (V, E) consists of a set of complexity. This four-level hierarchy, called the Chomsky Hierarchy, vertices V = {v1, v2, v3,…} and a set of edges E = {e1, e2, e3,…} (Kandar, 2013). corresponds to four (4) classes of machines. Each higher level in the hierarchy incorporates the lower levels. This means that anything that can Directed Graph – A graph with edges that has a direction (with arrow be computed by a machine at the lowest level can also be computed by a heads). Edges are represented by ordered pairs. See Figure 1. machine at the next higher level. It classifies grammars according to the Undirected Graph – graph with edges that has no direction (without form of their productions (rules). arrow heads). Edges are represented by unordered pairs. See Figure 2. a. Type 0 grammar - Unrestricted grammar (URG): This defines recursively enumerable languages. In URGs, all the productions are of the form α → β where α and β may have any number of terminals 02 Handout 1 *Property of STI  [email protected] Page 1 of 3  IT2005 There is a specially designed vertex called root which has no predecessors and from which there is a path to every vertex. The rest of the nodes that could be partitioned into t-disjoint sets (t ≥ 0), where each set represents a tree Ti. i = 0 to t, called subtrees. The vertex of a tree having one (1) degree is called the leaf node or terminal node. The nodes other than the leaf nodes are called the non-terminal nodes. In a rooted tree, vertex p is the parent of vertex q if p immediately Figure 1. Example of a directed graph. precedes q on the path from the root to q. Vertex p is the parent of q if and Source: Formal Language and Automata Theory, 2015 p. 16 only if q is a child of p (www-math.ucdenver.edu, n.d.). In a rooted tree, a vertex q is a child of vertex p if q immediately succeeds p on the path from the root to q. Vertex q is a child of p if and only if p is the parent of q (www-math.ucdenver.edu, n.d.). Two (2) vertices in a rooted tree are considered siblings if they have the same parent. The depth of a node is the length of the path, or the number of edges from the root of the tree to the target node. The root node has a depth zero (0). The set of all nodes at a given depth is called the level of the tree. The height of a tree is the length of the path from the root to the deepest Figure 2. Example of an undirected graph. node in the tree. Source: Formal Language and Automata Theory, 2015 p. 17 Incident – This occurs when an edge meets a vertex (Kandar, 2013). Degree – This pertains to the number of edges incident on a vertex. If the edge has a self-loop, it will be counted twice (Kandar, 2013). Isolated Vertex – This refers to a vertex of a graph having no incident edge (Kandar, 2013). Pendant Vertex – This refers to a vertex of degree one (1). It is sometimes called as an end vertex (Kandar, 2013). Figure 3. An example of a tree. Walk/Path – It is a finite alternating sequence of vertices and edges, starting and ending with vertices. In a single walk, no edge must be traversed more Theorem Proving than once, whereas a vertex may be traversed more than once. If the Theorem – a formula, proposition, or statement that can be logically true by beginning and end vertices of a walk are the same, then it is called closed proving (Merriam-Webster, n.d.). walk, or else it is considered as an open walk. (Kandar, 2013). Proof by Induction – This is a mathematical technique which is used to prove a statement, a formula, or a theorem to be true for every natural Tree – It is defined as an undirected graph composed of vertices and edges number. The following are the two major steps of proof by induction with the following properties (Kandar, 2013): (Tutorialspoint.com, n.d.): 02 Handout 1 *Property of STI  [email protected] Page 2 of 3  IT2005 1. Base Step: This step proves that a statement is true for the initial Step 2: There are four (4) cases to consider for p and q. value. Case1: If p and q are both odd, then the left-hand side (LHS) of the 2. Inductive Step: This step proves that if the statement is true for the above equation is odd. But zero (0) is not odd, which leaves a nth iteration or a number k, therefore it is also true for (n + 1)th iteration contradiction. or a number k + 1. Case2: If p is even and q is odd, then the LHS is odd, again a Example: Prove by induction that n4 – 4n2 is divisible by 3 for n ≥ 0. contradiction. Solution: Case3: If p is odd and q is even, the same contradiction occurs. Base Step: Case4: If p and q are even, it is not possible because of the For n = 0, n4 – 4n2 = 0 that is divisible by 3. assumption that p/q is in reduced form. Inductive Step: This completes the proof. Inductive hypothesis: Let n4 – 4n2 is divisible by 3. = (n + 1)4 - 4(n + 1)2 Proof by Example – This is the simplest technique of proving. It involves = ((n + 1)2)2 - 4(n + 1)2 deriving conclusions based on one or more examples. = (n2 + 2n + 1)2 - (2n + 2)2 Example: Prove by example that the sum of an odd and an even number = (n2 + 2n + 1 + 2n + 2) (n2 + 2n + 1 - 2n - 2) is always odd. Since the equation above is of the form a2 - b2 = (a + b)(a - b), Solution: = (n4 + 4n + 3) (n2 - 1) Let the even number be x = 2k where k is some natural number. = n4 + 4n3 + 3n2 - 3 - 4n - n2 Let the odd number be y = 2q + 1 where q is some natural number. = (n4 - 4n2) + (6n2 – 3) + 4(n3 - n)  (1) Prove that sum of x and y is always odd. Now prove that (n3 - n) is divisible by 3. x + y = 2k + 2q + 1 = 2(k + q) + 1 Basis for n = 0, n3 - n = 0 is divisible by 3. k and q are natural numbers. True for k + 1 Hence k + q is also a natural number. = (k + 1)3 - (k + 1) Therefore, 2(k + q) + 1 is always odd. = (k3 + 3k2 + 3k + 1) - (k + 1) = k3 + 3k2 + 2k References: = (k3 - k) + 3k2 + 3k Graph and Digraph Glossary. (n.d.). In University of Colorado Denver. Retrieved from http://www- divisible by 3. math.ucdenver.edu/~wcherowi/courses/m4408/glossary.html on June 16, 2020 Kandar, S. (2013). Introduction to Automata Theory , Formal Languages and Computation. Dorling Hence (1) is divisible by 3. Kindersley (India) Pvt. Ltd. Thus proved. Merriam-Webster. (n.d.). Theorem. In Merriam-Webster.com dictionary. Retrieved from https://www.merriam-webster.com/dictionary/theorem on June 16, 2020 Proof by Contradiction – This proving technique involves the logical Sunitha, K. & Kalyani, N. (2016). Formal Language and Automata Theory. Pearson India Education negation of the expected result, and come up with a contradiction. Services Pvt. Ltd. Example: Prove by contradiction that there are no rational number Tutorialspoint. (n.d). Mathematical Induction. In Tutorialspoint.com. Retrieved from https://www.tutorialspoint.com/discrete_mathematics/discrete_mathematical_induction.htm on solutions to the equation x3 + x + 1 = 0. June 16, 2020 Solution: Step 1: Assume the contrary that there is a rational number p/q, in reduced form, with p not equal to 0, which satisfies the equation. Then, p3/q3 + p/q + 1 = 0. Multiplying each side of the equation by q3. The equation will now be: p3 + pq2 + q3 = 0 02 Handout 1 *Property of STI  [email protected] Page 3 of 3