Theory of Computation- Lecture Notes - University of South ...

1 Theory of computation - Lecture NotesMichael LevetAugust 27, 2019 Contents1 Mathematical Set Theory .. relations and Functions .. relations .. Proof by Induction .. Brief Review of Asymptotics .. Combinatorics and Graph Theory .. Enumerative Techniques .. Proofs .. Theory .. Number Theory .. Russell s Paradox and Cantor s Diagonal Argument ..242 Automata Regular Languages .. Finite State Automata .. Converting from Regular Expressions to -NFA .. Algebraic Structure of Regular Languages .. DFAs, NFAs, and -NFAs .. DFAs to Regular Expressions- Brzozowski s Algebraic Method .. Pumping Lemma for Regular Languages .. Closure Properties .. Myhill-Nerode and DFA Minimization ..443 More Group Theory (Optional) Introductory Group Theory .

2 To Groups .. Group .. Group .. Homomorphisms and Isomorphisms .. Actions .. Graph Theory - Cayley Graphs .. Graph Theory - Transposition Graphs .. Subgroups .. Groups .. Generated By Subsets of a Group .. Poset and Lattice (Hasse) Diagram .. Quotient Groups .. to Quotients .. Subgroups and Quotient Groups .. on Cosets and Lagrange s Theorem .. Group Isomorphism Theorems .. Group .. Graph Theory - Graph Homomorphisms .. Combinatorics- The Determinant .. Group Actions .. of Groups .. s Theorems .. of Sylow s Theorems .. Combinatorics- P olya Enumeration Theory ..934 Turing Machines and Computability Standard Deterministic Turing Machine .. Variations on the Standard Turing Machine .. Turing Machine Encodings.

3 Chomsky Heirarchy and Some Decidable Problems .. Undecidability .. Reducibility .. 1025 Complexity Time Complexity-PandNP.. More onPandP-Completeness .. Closure Properties ofNPandP.. Structural Proofs forNPandP.. Ladner s Theorem .. Impagliazzo s Proof of Ladner s Theorem .. 11921 Mathematical Set TheoryDefinition 1(Set).Asetis collection of distinct elements, where the order in which the elements are listeddoes not matter. The size of a setS, denoted|S|, is known as itscardinalityororder. The members of a setare referred to as its elements. We denote membership ofxinSasx S. Similarly, ifxis not inS, we denotex6 examples of sets include the set of real numbersR,the set of rational numbersQ, andthe set of integersZ.

4 The setsR+,Q+andZ+denote the strictly positive elements of the reals, rationals,and integers respectively. We denote the set of natural numbersN={0,1,..}. Letn Z+and denote[n] ={1,..,n}.We now review several basic set operations, as well as the power set. It is expected that students will befamiliar with these constructs. Therefore, we proceed briskly, recalling definitions and basic examples intendedsolely as a Union LetA,Bbe sets. Then theunionofAandB, denotedA Bis the set:A B:={x:x Aorx B}Example {1,2,3}andB={4,5,6}. ThenA B={1,2,3,4,5,6}.Example {1,2,3}andB={3,4,5}. SoA B={1,2,3,4,5}. Recall that sets do not containduplicate elements. So even though 3 appears in bothAandB, 3 occurs exactly once inA Intersection LetA,Bbe sets.

5 Then theintersectionofAandB, denotedA Bis the set:A B:={x:x Aandx B}Example {1,2,3}andB={1,3,5}. ThenA B={1,3}. Now letC={4}. SoA C= .Definition 4(Symmetric Difference).LetA,Bbe sets. Then thesymmetric differenceofAandB, denotedA4 Bis the set:A4B:={x:x Aorx B, butx6 A B}Example {1,2,3}andB={1,3,5}. ThenA4B={2,5}.For our next two definitions, we letUbe ouruniverse. That is, letUbe a set. Any sets we consider are 5(Set Complementation).LetAbe a set contained in our universeU. ThecomplementofA,denotedACorA, is the set:A:={x U:x6 A}Example [5], and letA={1,2,4}. ThenA={3,5}.Definition 6(Set Difference).LetA,Bbe sets contained in our universeU. ThedifferenceofAandB,denotedA\BorA B, is the set:A\B={x:x Aandx6 B}Example [5],A={1,2,3}andB={1,2}. ThenA\B={3}.

6 Remark:The Set Difference operation is frequently known as therelative complement, as we are taking thecomplement ofBrelative toArather than with respect to the 7(Cartesian Product).LetA,Bbe sets. TheCartesian productofAandB, denotedA B, isthe set:A B:={(a,b) :a A,b B}Example {1,2,3}andB={a,b}. ThenA B={(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)}. 3 Definition 8(Power Set).LetSbe a set. Thepower setofS, denoted 2 SorP(S), is the set of all subsetsofS. Formally:2S:={A:A S}Example {1,2,3}. So 2S={ ,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}. Remark:For finite setsS,|2S|= 2|S|; hence, the choice of 9(Subset).LetA,Bbe said to be asubsetofBif for everyx A, we havex Baswell. This is denotedA B(equivocally,A B). Note thatBis [3],B= [6],C={2,3,5}. So we haveA BandC B. However,A6 Cas 16 C;andC6 A, as 56 :LetSbe a set.

7 The subset relation forms a partial order on 2S. To show two setsAandBareequal, we must showA BandB A. We demonstrate how to prove two sets are equal {6n:n Z},B={2n:n Z},C={3n:n Z}. SoA=B first show thatA B C. Letn Z. So 6n A. We show 6n B C. As 2 is a factor of 6,6n= 2 (3n) B. Similarly, as 3 is a factor of 6, 6n= 3 (2n) C. So 6n B C. We now show thatB C A. Letx B C. Letn1,n2 Zsuch thatx= 2n1= 3n2. As 2 is a factor ofxand 3 is a factor ofx, it follows that 2 3 = 6 is also a factor ofx. Thus,x= 6n3for somen3 Z. Sox A. Thus,B C ,A=B C, as ,B,Cbe sets. ThenA (B C) = (A B) (A C). (x,y) A (B C). Ify B, then (x,y) (A B). Otherwise,y Cand so (x,y) (A C).Thus,A (B C) (A B) (A C). Now let (d,f) (A B) (A C). Clearly,d A. Sofmust bein eitherBorC.

8 Thus, (d,f) A (B C), which implies (A B) (A C) A (B C). We concludethatA (B C) = (A B) (A C). relations and FunctionsDefinition 10(Relation).LetXbe a set. Ak-ary relation onXis a subsetR notion of equality = overRis the canonical example of a relation. It is perhaps the mostwell-known instance of anequivalence relation, which will be discussed , ak-ary relationRcontainsk-tuples of elements fromXthat share common properties. Computerscientists and mathematicians are interested in a number of different relations , including the adjacency relation(graph Theory ), equivalence relations , orders (such as partial orders), and functions. In this section, functions,asymptotics, and equivalence relations will be FunctionsThe notion of afunctionwill be introduced first.

9 Functions are familiar mathematical objects, which appearearly on in mathematics education with the notion of an input-output machine. Roughly speaking, a functiontakes an input and produces an output. Some common examples include the linear equationf(x) =ax+band the exponentialf(x) = denote a function as follows. LetXandYbe sets. A function is a mapf:X Ysuch that for everyx X, there is a uniquey Ywheref(x) =y. We say thatXis thedomainandYis thecodomain. Therangeorimageis the setf(X) ={f(x) :x X}. More formally, a function is defined as follows:Definition LetXandYbe sets. A functionfis a subset (or 1-place relation) ofX Ysuchthat for everyx X, there exists a uniquey Ywhere (x,y) s consider some formal functions and one example of a relation that is not a :R Rbe given byf(x) =x.

10 This is known as theidentity :R Rbe given byg(x) = :R Rgiven by:h(x) ={x:x6= 3 3,2 :x= 3 Note thathisnota function as (3, 3) hand (3,2) h. The definition of a function states that there mustbe auniqueysuch that (3,y) h. If we revisehsuch thath(3) = 3only, thenhsatisfies the definition of a combinatorial perspective, special types of functions known asinjectionsandsurjectionsare of greatimportance. The idea is that if we have two setsXandYand know the cardinality ofX, then an injection orsurjection fromXtoYyields results aboutY s cardinality. We can deduce similar results aboutY s injection is also known as aone-to-onefunction. Recall the definition of a function states that the mapf:X Ymaps eachx Xto a uniquey Y. It allows for functions such asg:R Rgiven byg(x) = 0.}