[PDF] Theory of Computation- Lecture Notes PDF Lecture

27 août 2019 · 2 Automata Theory Theoretical computer science is divided into three key areas: automata theory, computability theory, and complexity theory

17 avr 2019 · Introduction to Languages and the Theory of Computation (third edi- tion), by John Martin, McGraw-Hill, 2003 • Introduction to Automata Theory

[PDF] Introduction to the Theory of Computation, 3rd ed - Bad Request

of the correctness of various constructions concerning automata If presented clearly, these constructions convince and do not need further argument An in-

[PDF] Introduction To The Theory Of Computation - Michael Sipser

Remember finite automata and regular expressions Confronted with a problem that seems to re- quire more computer time than you can afford? Think back to

[PDF] Theory of Computation- Lecture Notes

27 août 2019 · 2 Automata Theory Theoretical computer science is divided into three key areas: automata theory, computability theory, and complexity theory

[PDF] Introduction to the Theory of Computation - Department of Computer

Automata theory 5 1 Undecidable Problems from Language Theory puter science or engineering, and a course in theory is required-God knows

[PDF] Introduction to theory of computation - Tom Carter

areas of automata theory, computability, and formal languages In various respects, this can be thought of as the elementary foundations of much of computer

[PDF] Introduction to the Theory of Computation - CIn UFPE

1 Regular Languages 1 1 Finite Automata Formal definition of a finite automaton Examples of finite automata

[PDF] Introduction to Theory of Computationpdf

25 sept 2014 · Introduction to Automata Theory, Languages, and Computation (third edition) Purpose of the Theory of Computation: Develop formal math-

[PDF] The Theory of Languages and Computation - UPenn CIS

turns out to be the crucial fact in proving many non-trivial things about finite state automata The formal mathematical statement of the pigeon hole principle is

[PDF] Theory of Computation: An Introduction

automata, computability, and complexity These areas are linked by the question: What are the fundamental capabilities and limitations of computers?

[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

[PDF] Theory of Computation- Lecture Notes

Theory of Computation- Lecture Notes

Michael Levet

August 27, 2019

1 Mathematical Preliminaries 3

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

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

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

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

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

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

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

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

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

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

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

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

2 Automata Theory25

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

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

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

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

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

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

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

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

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

3 More Group Theory (Optional) 48

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

81
1

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

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

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

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

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

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

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

4 Turing Machines and Computability Theory 93

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

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

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

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

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

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] [PDF] Theory of Computation- Lecture Notes