ACM MONOGRAPH SERIES Published under the auspices of the Association for Computing Machinery Inc. Edited by ROBERT L. ASHENHURST The University of Chicago A. FiNERMAN (Ed.) University Education in Computing Science, 1968 A. GINZBURG Algebraic Theory of Automata, 1968 In preparation E. F. CoDD Cellular Automata G. ERNST AND A. NEWELL GPS: A Case Study in Generality and Problem Solving Previously published and available from The Macmillan Company, New York City G. SEBESTYN Decision Making Processes in Pattern Recognition, 1963 M. YoviTS (Ed.) Large Capacity Memory Techniques for Computing Sys- tems, 1962 V. KRYLOV Approximate Calculation of Integrals (Translated by A. H. Stroud), 1962 Algebraic Theory of Automata Abraham Ginzburg CARNEGIE-MELLON UNIVERSITY PITTSBURGH, PENNSYLVANIA THE TECHNION ISRAEL INSTITUTE OF TECHNOLOGY HAIFA, ISRAEL ACADEMIC PRESS New York · London 1968 COPYRIGHT © 1968, BY ACADEMIC PRESS INC. ALL RIGHTS RESERVED. NO PART OF THIS BOOK MAY BE REPRODUCED IN ANY FORM, BY PHOTOSTAT, MICROFILM, OR ANY OTHER MEANS, WITHOUT WRITTEN PERMISSION FROM THE PUBLISHERS. ACADEMIC PRESS INC. 111 Fifth Avenue, New York, New York 10003 United Kingdom Edition published by ACADEMIC PRESS INC. (LONDON) LTD. Berkeley Square House, London W. 1 LIBRARY OF CONGRESS CATALOG CARD NUMBER: 68-23492 PRINTED IN THE UNITED STATES OF AMERICA Preface This monograph is intended to provide a graduate student and a new- comer to the field with ideas, methods, and results of algebraic theory of automata; nevertheless, people working in the area may find the book useful, too, especially the chapters about regular expressions and the decomposition theory of Krohn and Rhodes. The book can serve as a text for a one-semester course in Automata Theory. The contents of the monograph need not be discussed here (see the Table of Contents) but for the following two remarks: 1. The purpose of Chapter 1 is to enable the reader with a weaker algebraic preparation to study the book without too many detours to an algebra text. 2. The limited scope of the publication and the desire to cover the topics with appropriate depth excluded automatically some aspects of the subject; the choice was largely biased by the author's per- sonal interests. The relational representation of automata is used in this book. Coupled with several additional techniques it proves to be a very convenient tool to deal with the theory of finite automata. Many results allow shorter and simpler proofs, and new insight is often gained. The regular expressions are treated by means of transition graphs and tables of derivatives, thus avoiding the usual quite cumbersome algebraic manipulations. The bibliography contains mainly titles that are referred to directly. The author is grateful to the ACM and Academic Press for their willingness to include this book in the ACM Monograph Series, and to the Advanced Research Projects Agency of the Office of the Secretary of Defense (SD-146) for supporting this work. Sincere thanks are due to Mrs. Dorothy Josephson, from the unusually efficient office of the Computer Science Department at Carnegie-Mellon VI PREFACE University of Pittsburgh, for her devotion, patience, and skill in typing this sub-superscript material. Professor David Parnas, Mrs. Carol Thompson, Mr. Zohar Manna, and Dr. Abraham Lempel read parts of the manuscript, and their criticism and remarks are greatly appreciated. Special thanks are due to Professor Albert R. Meyer for his help in improving the manuscript. Section 7.12 and a large portion of Section 5,6 which were written by him together with his numerous suggestions, comments, and corrections make his contribution to this book extremely valuable. Finally, the author is greatly indebted to the Computer Science and Mathematics Departments at Carnegie-Mellon University, and especi- ally to the heads of these departments. Professor Alan J. Pedis and Professor Ignace I. Kolodner, for the privilege of doing this work in a most inspiring and generous atmosphere, and for their constant en- couragement and assistance. Pittsburgh, Pennsylvania ABRAHAM GINZBURG Chapter 1 Algebraic Preliminaries Algebraic notions and connections used later are presented in this chapter. Many readers will presumably prefer only to scan it briefly and return when necessary to specific facts and theorems discussed here. 1.1 Sets The symbol Ρ => β indicates that Ρ implies Q, i.e., if Ρ is true then Q is true. The symbol Ρ ο Q indicates that Ρ implies Q and Q implies P; in words: Ρ if and only if β. The notions of a set and an element of a set are considered as basic and taken without definition. The following notations are also used: {a I JP} the set of all such elements a (from some set) which satisfy the property P. ae A α is an element of the set A. αφ A a is not an element of the set A. φ the empty set, i.e., the set which does not contain any elements. Let A and Β be sets. IfaeA ^ aeB then A is said to be a subset of B, which is denoted by A ^ Β or Β ^ A. For every set A, φ ^ A, A ^ A, 2 1 ALGEBRAIC PRELIMINARIES A = Β ο A ^ Β Sind Β ^ A, Au Β denotes the (set theoretical) union of the sets A and B, which is the set of all elements belonging to A or to B, or to both. A r\ B, the intersection of A and B, is the set of all elements belonging to A and Β simultaneously. Clearly, AuB = A o A nB = B o A ^ B. A - Bis the set of all elements in A which are not in B. The set of all ordered pairs (a, b) (aeA,be B) is called the Cartesian product of A and Β and is denoted by A χ B. Similarly, one defines a Cartesian product of any finite number of sets. 1.2 Relations and Mappings Any subset of ^ χ Bis called a {binary) relation between A and B. Let Ä be a relation between A and B, i.e., JR is a set of pairs (a, b), where as A, beB. (a,b)eR is often expressed also in the form ^ e R or aRb. The inverse relation R~^ is defined by b R-^ aoaRb. Ρ "Ms a relation between Β and A. Relations between A and A will be mostly considered; they are said to be relations over A. If Ris SL relation over A, so is R~^. pr^R = {a \ lb, a Rb) is the set of all such a's for which there exists at least one b such that aRb holds. pr^R = priR'^, that is przR = {b\3a,aRb}, By definition, pr^R ^ A, przR ^ B, pr^R is also called the domain of R, pr2R is called the range of R. A relation ψ satisfying: a φ bi, a φ b2 bi = 62 1.3 GROUPOIDS, SEMIGROUPS 3 (in words: every element of ρΓιψ is in relation φ with exactly one element of B) is called a mapping from A into B. In other words, φ is a mapping from the set A into the set Β if φ "assigns" to every element of some subset of A (called the domain of φ) one and only one element of B, Distinct elements of A can be, of course, mapped by φ on the same element of B. If prιφ = A, then 9? is a mapping of A into B, If prιφ = A and pr29 = B, then 9? is a mapping of A onto B. A mapping is often also called a function. The image of a under the mapping φ is denoted by φ(α) or αφ. For any relation, R(d) = aR = {b\aRb}, For ^1 g A, U R(A,) = A,R= R(ä). aeAi If 95 is a mapping, φ-^ need not be. In case it is, φ is called a one-to-one mapping. In other words, 93 is a one-to-one mapping from A into 5 if 9? is a mapping from A into B, and for any two distinct ^i, öfg in the domain of φ: φ(αι) φ ψ{α^. In this case φ "Ms a mapping of the range of ψ (a subset of B) onto the domain of 9? (a subset of A). The sets A and Β are said to have the same cardinality if there exists a one-to-one mapping of A onto B. In the finite case this means that A and Β have the same number of elements. In the infinite case, a proper (i.e., distinct from A) subset of a set A may have the same cardinality as A (e.g., the even integers and all integers). Moreover, this property charac- terizes infinite sets. A one-to-one mapping of a set A onto itself is called a permutation. If φ is a permutation, then 9?"^ is, too. 1.3 Groupoids, Semigroups A set A with a mapping ψ from the Cartesian product A χ A into A forms a partial binary single-valued multiplicative system (or, briefly, a partial binary system), usually also denoted by A. 4 1 ALGEBRAIC PRELIMINARIES In Other words, ^ is a partial binary system if there is defined an operation (called, say, multiplication) in A, which "combines" some ordered pairs of elements of A to give, in result, an element of A, One writes instead of (^i, 02)9^ = 0^3 simply ^1^2 = (Ö1, Ä2> ÖTg Ε A), If the operation is defined for all pairs of ^4 χ >4 it is called total, and A, with that operation, is called a (complete) binary system or groupoid, A finite groupoid can be conveniently described by a "multiplication table" similar to those from elementary arithmetic. The operation in a groupoid can be subject to certain axioms. In particular, the so-called associativity is very often required: For every a,b,ce A {ab)c = aibc). An induction proof can be provided to the eff*ect that the above implies that the product of an arbitrary number of elements in A will be independent on the particular arrangement of brackets. A groupoid fulfilUng the axiom of associativity is called an associative groupoid, or a semigroup. In a semigroup one writes abc without brackets, and can apply the usual power notation\ α'^ΐον aa.. .a {n times) with the familiar laws: a^a^ = a"^"*"^, (a^)^ = a"^"^. The positive integers form a semigroup under addition and also under multiplication. The following multiplication tables describe two semi- groups, each one consisting of three elements: a 0 1 2 a bc 0 1 2 b b c 1 2 0 c b c 2 0 1 A semigroup, which is of particular importance in the sequel, will now be described. Let Σ = {σο, cTi,..., σ;„_ι} be a finite set of symbols called, also, letters; accordingly, Σ is called an alphabet. 1.3 GROUPOIDS, SEMIGROUPS 5 A word (often called, also, a siring, or a tape) over Σ is a finite sequence of letters from Σ written one after the other without any intermediate signs. (For example, 0^02, agai, σοσ3σ,„_ισ3σ3 are words over Σ. Notice that σισ2 and agaj are distinct words.) One considers, also, the so-called empty word, i.e., the word which does not have any letters; it is denoted by Λ. The length of a word is the number of letters in it. The length of Λ is 0. Σ* denotes the set of all words over Σ (including the empty one) with the operation of concatenation of words which combines to one word an ordered pair of words by writing the letters of the second after those of the first. For example, 0^ΐΟ'3θ'3^2 * ^0^2^1 — O^lO'3O'3O"2^0^2<^l« For Λ one has by definition, wA = Λ w = w for every word w in Σ*. Thus, Σ* is a groupoid; moreover, it is a semigroup, because the above operation is evidently associative. This semigroup is called the free semi- group generated by Σ, and the set Σ is called the set of generators of Σ*. Another important example of a semigroup is provided by the rela- tions over a set ^. Let R and S be two relations over A. The relation Γ defined as follows: a T b o lc suchthat aRc and cSb is called the composition or the product of R and S (in this order): T= RS. Notice: RS = φο pr2R π priS = φ. The composition of relations is associative. Indeed, a (RS)Tb ο 3 x(a RS χ, χ Τb) ο 3 χ 3 y(a R y, y S χ, χ Tb) o3 y(aRy,y STb) ο a R(ST)b. Thus, the set of all relations over A with the above defined multiplication forms a semigroup.