01_Handout_1(Theory of Computation with Automata).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