[PDF] Theory of Computation- Lecture Notes

View - Download Theory of Computation- Lecture Notes

Previous PDF

Next PDF

Theory of Computation- Lecture Notes

Michael Levet

August 27, 2019

Contents

1 Mathematical Preliminaries 3

1.1 Set Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.2 Relations and Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.2.1 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.2.2 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.3 Proof by Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

1.3.1 A Brief Review of Asymptotics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

1.4 Combinatorics and Graph Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

1.4.1 Basic Enumerative Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

1.4.2 Combinatorial Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

1.4.3 Graph Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

1.5 Number Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

1.6 Russell's Paradox and Cantor's Diagonal Argument . . . . . . . . . . . . . . . . . . . . . . . . .

24

2 Automata Theory25

2.1 Regular Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

2.2 Finite State Automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

2.3 Converting from Regular Expressions to-NFA . . . . . . . . . . . . . . . . . . . . . . . . . . .31

2.4 Algebraic Structure of Regular Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

2.5 DFAs, NFAs, and-NFAs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .34

2.6 DFAs to Regular Expressions- Brzozowski's Algebraic Method . . . . . . . . . . . . . . . . . . .

37

2.7 Pumping Lemma for Regular Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

2.8 Closure Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

2.9 Myhill-Nerode and DFA Minimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

3 More Group Theory (Optional) 48

3.1 Introductory Group Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

3.1.1 Introduction to Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

3.1.2 Dihedral Group . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

50

3.1.3 Symmetry Group . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

3.1.4 Group Homomorphisms and Isomorphisms . . . . . . . . . . . . . . . . . . . . . . . . .

55

3.1.5 Group Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

56

3.1.6 Algebraic Graph Theory- Cayley Graphs . . . . . . . . . . . . . . . . . . . . . . . . . .

58

3.1.7 Algebraic Graph Theory- Transposition Graphs . . . . . . . . . . . . . . . . . . . . . . .

60

3.2 Subgroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

3.2.1 Cyclic Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

64

3.2.2 Subgroups Generated By Subsets of a Group . . . . . . . . . . . . . . . . . . . . . . . .

66

3.2.3 Subgroup Poset and Lattice (Hasse) Diagram . . . . . . . . . . . . . . . . . . . . . . . .

66

3.3 Quotient Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

3.3.1 Introduction to Quotients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

3.3.2 Normal Subgroups and Quotient Groups . . . . . . . . . . . . . . . . . . . . . . . . . . .

70

3.3.3 More on Cosets and Lagrange's Theorem . . . . . . . . . . . . . . . . . . . . . . . . . .

73

3.3.4 The Group Isomorphism Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

76

3.3.5 Alternating Group . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

79

3.3.6 Algebraic Graph Theory- Graph Homomorphisms . . . . . . . . . . . . . . . . . . . . .

81
1

3.3.7 Algebraic Combinatorics- The Determinant . . . . . . . . . . . . . . . . . . . . . . . . .84

3.4 Group Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

84

3.4.1 Conjugacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

84

3.4.2 Automorphisms of Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

88

3.4.3 Sylow's Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

88

3.4.4 Applications of Sylow's Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

91

3.4.5 Algebraic Combinatorics- Polya Enumeration Theory . . . . . . . . . . . . . . . . . . .

93

4 Turing Machines and Computability Theory 93

4.1 Standard Deterministic Turing Machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

93

4.2 Variations on the Standard Turing Machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

96

4.3 Turing Machine Encodings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

98

4.4 Chomsky Heirarchy and Some Decidable Problems . . . . . . . . . . . . . . . . . . . . . . . . .

98

4.5 Undecidability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

101

4.6 Reducibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

102

5 Complexity Theory103

5.1 Time Complexity-PandNP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .104

5.2NP-Completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .106

5.3 More onPandP-Completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .111

5.4 Closure Properties ofNPandP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .114

5.5 Structural Proofs forNPandP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .114

5.6 Ladner's Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

114

5.6.1 Russell Impagliazzo's Proof of Ladner's Theorem . . . . . . . . . . . . . . . . . . . . . .

117

5.7PSPACE. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .119

5.8PSPACE-Complete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .119

2

1 Mathematical Preliminaries

1.1 Set Theory

Denition 1(Set).Asetis collection of distinct elements, where the order in which the elements are listed

does not matter. The size of a setS, denotedjSj, is known as itscardinalityororder. The members of a set

are referred to as its elements. We denote membership ofxinSasx2S. Similarly, ifxis not inS, we denote

x62S. Example 1.Common examples of sets include the set of real numbersR;the set of rational numbersQ, and

the set of integersZ. The setsR+;Q+andZ+denote the strictly positive elements of the reals, rationals,

and integers respectively. We denote the set of natural numbersN=f0;1;:::g. Letn2Z+and denote [n] =f1;:::;ng.

We now review several basic set operations, as well as the power set. It is expected that students will be

familiar with these constructs. Therefore, we proceed briskly, recalling denitions and basic examples intended

solely as a refresher. Denition 2.Set Union LetA;Bbe sets. Then theunionofAandB, denotedA[Bis the set:

A[B:=fx:x2Aorx2Bg

Example 2.LetA=f1;2;3gandB=f4;5;6g. ThenA[B=f1;2;3;4;5;6g. Example 3.LetA=f1;2;3gandB=f3;4;5g. SoA[B=f1;2;3;4;5g. Recall that sets do not contain duplicate elements. So even though 3 appears in bothAandB, 3 occurs exactly once inA[B. Denition 3.Set Intersection LetA;Bbe sets. Then theintersectionofAandB, denotedA\Bis the set:

A\B:=fx:x2Aandx2Bg

Example 4.LetA=f1;2;3gandB=f1;3;5g. ThenA\B=f1;3g. Now letC=f4g. SoA\C=;. Denition 4(Symmetric Dierence).LetA;Bbe sets. Then thesymmetric dierenceofAandB, denoted

A4Bis the set:

A4B:=fx:x2Aorx2B, butx62A\Bg

Example 5.LetA=f1;2;3gandB=f1;3;5g. ThenA4B=f2;5g.

For our next two denitions, we letUbe ouruniverse. That is, letUbe a set. Any sets we consider are subsets

ofU. Denition 5(Set Complementation).LetAbe a set contained in our universeU. ThecomplementofA, denotedACorA, is the set:A:=fx2U:x62Ag Example 6.LetU= [5], and letA=f1;2;4g. ThenA=f3;5g. Denition 6(Set Dierence).LetA;Bbe sets contained in our universeU. ThedierenceofAandB, denotedAnBorAB, is the set:

AnB=fx:x2Aandx62Bg

Example 7.LetU= [5],A=f1;2;3gandB=f1;2g. ThenAnB=f3g.

Remark:The Set Dierence operation is frequently known as therelative complement, as we are taking the

complement ofBrelative toArather than with respect to the universeU. Denition 7(Cartesian Product).LetA;Bbe sets. TheCartesian productofAandB, denotedAB, is the set:

AB:=f(a;b) :a2A;b2Bg

Example 8.LetA=f1;2;3gandB=fa;bg. ThenAB=f(1;a);(1;b);(2;a);(2;b);(3;a);(3;b)g. 3 Denition 8(Power Set).LetSbe a set. Thepower setofS, denoted 2SorP(S), is the set of all subsets ofS. Formally: 2

S:=fA:ASg

Example 9.LetS=f1;2;3g. So 2S=f;;f1g;f2g;f3g;f1;2g;f1;3g;f2;3g;f1;2;3gg. Remark:For nite setsS,j2Sj= 2jSj; hence, the choice of notation. Denition 9(Subset).LetA;Bbe sets.Ais said to be asubsetofBif for everyx2A, we havex2Bas well. This is denotedAB(equivocally,AB). Note thatBis asupersetofA. Example 10.LetA= [3];B= [6];C=f2;3;5g. So we haveABandCB. However,A6Cas 162C; andC6A, as 562A. Remark:LetSbe a set. The subset relation forms a partial order on 2S. To show two setsAandBare equal, we must showABandBA. We demonstrate how to prove two sets are equal below. Proposition 1.1.LetA=f6n:n2Zg;B=f2n:n2Zg;C=f3n:n2Zg. SoA=B\C. Proof.We rst show thatAB\C. Letn2Z. So 6n2A. We show 6n2B\C. As 2 is a factor of 6,

6n= 2(3n)2B. Similarly, as 3 is a factor of 6, 6n= 3(2n)2C. So 6n2B\C. We now show that

B\CA. Letx2B\C. Letn1;n22Zsuch thatx= 2n1= 3n2. As 2 is a factor ofxand 3 is a factor of x, it follows that 23 = 6 is also a factor ofx. Thus,x= 6n3for somen32Z. Sox2A. Thus,B\CA. Thus,A=B\C, as desired.Proposition 1.2.LetA;B;Cbe sets. ThenA(B[C) = (AB)[(AC). Proof.Let (x;y)2A(B[C). Ify2B, then (x;y)2(AB). Otherwise,y2Cand so (x;y)2(AC). Thus,A(B[C)(AB)[(AC). Now let (d;f)2(AB)[(AC). Clearly,d2A. Sofmust be in eitherBorC. Thus, (d;f)2A(B[C), which implies (AB)[(AC)A(B[C). We conclude thatA(B[C) = (AB)[(AC).1.2 Relations and Functions Denition 10(Relation).LetXbe a set. Ak-ary relation onXis a subsetRXk.

Example 11.The notion of equality = overRis the canonical example of a relation. It is perhaps the most

well-known instance of anequivalence relation, which will be discussed later.

Intuitively, ak-ary relationRcontainsk-tuples of elements fromXthat share common properties. Computer

scientists and mathematicians are interested in a number of dierent 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 discussed.

1.2.1 Functions

The notion of afunctionwill be introduced rst. Functions are familiar mathematical objects, which appear

early on in mathematics education with the notion of an input-output machine. Roughly speaking, a function

takes an input and produces an output. Some common examples include the linear equationf(x) =ax+bquotesdbs_dbs2.pdfusesText_3

[PDF] theory of quadratic equation

[PDF] theory of semiotics ferdinand de saussure pdf

[PDF] therapeutic drug monitoring pdf

[PDF] therapeutic drug monitoring ppt

[PDF] therapeutic drug monitoring principles

[PDF] therapeutic drug monitoring review

[PDF] thermal model of a house

[PDF] thermostat simulink

[PDF] thesis about british and american english

[PDF] thesis on android application development

[PDF] thesis outline example

[PDF] thirty years war essay question

[PDF] thirty years war essay thesis

[PDF] thirty years war political causes

[PDF] thirty years' war