Toc notes PDF

Preview

Summary

Five unit Notes for Theory of Computation...

Description

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

CS8501 - THEORY OF COMPUTATION (FOR III YEAR V SEM STUDENTS)

UNIT I to V

PREPARED BY S.RADHA AP/CSE

ACADEMIC CO-ORDINATOR

HOD

DEAN – ACADEMICS

PRINCIPAL

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING SENGUNTHAR ENGINEERING COLLEGE, TIRUCHENGODE LECTURE PLAN Subject Name

: THEORY OF COMPUTATION

Subject Code

: CS8501

Name of Faculty/Designation

: S.RADHA/AP

Course

: V SEMESTER B.E CSE

Academic year

: 2019-2020[ODD] RECOMMENDED TEXT BOOKS/REFERENCE BOOKS

S.NO

TITLE OF THE BOOK

AUTHOR

REFERENCE

1

Theory and Computation

A.A.Puntambekar

T1

Introduction to Automata Theory, Languages and Computation

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman

Introduction to Languages and the Theory of Computation

John C Martin

2

3

TOPIC

R1

R2

NO. OF HOURS

TEACHING AIDS

1

BB

1

BB

T1- Ch1.4,R2-Ch1

1

BB

T1- Ch1.1 to 1.3, R1-Ch1,R2-Ch1

1

BB

T1- Ch1.4,R2-Ch1

1

BB

T1-Ch1.6, R2-Ch1 T1-Ch1.6 to 1.10, R1-Ch2

1

BB

2

BB

REFERENCE

UNIT I - FINITE AUTOMATA Introduction to Formal proof Additional Forms of Proof Inductive Proof Introduction to Finite Automata Basic Mathematical Notations and Techniques Finite State Systems Finite Automaton, DFA& NDFA

T1- Ch1.1 to 1.3, R1-Ch1,R2-Ch1 T1- Ch1.1 to 1.3, R1-Ch1,R2-Ch1

Finite Automaton with €- moves

T1-Ch1.11, R1-Ch2

2

BB

UNIT II - REGULAR EXPRESSIONS AND LANGUAGES

Regular Languages- Regular Expression Equivalence of NFA and DFA Equivalence of NDFA’s with and without €-moves Equivalence of finite Automaton and regular expressions Minimization of DFA Pumping Lemma for Regular sets Problems based on Pumping Lemma.

T1-Ch2.1, R1-Ch3

1

BB

T1-Ch2.2, R1-Ch3

2

BB

T1-Ch2.7, R1-Ch3.2

2

BB

T1-Ch2.6,R2-Ch4.4

2

BB

T1-Ch2.11,R2-Ch5

1

BB

T1-Ch2.12,R2-Ch5

1

BB

UNIT –III CONTEXT FREE GRAMMAR AND LANGUAGES Grammar Introduction Types of Grammar - Context Free Grammars and Languages Ambiguity- Relationship between derivation and derivation trees Definition of Pushdown automataLanguages of a Pushdown Automata Moves - Instantaneous descriptions Deterministic pushdown automata Equivalence of Pushdown automata and CFL

T1- Ch3.1, R1-Ch5 T1- Ch3.1and 3.2, R1-Ch5 T1-Ch3.5 , 3.6,R1Ch5.4 T1- Ch4.1,4.3,R1-Ch6 T1- Ch4.2,R1-Ch6.1.4, R2-Ch8 T1- Ch4.5, R1-Ch6.4 T1- Ch4.6,R1-Ch6.3

1

BB

2

BB

1

BB

2

BB

2

BB

1

BB

2

BB

UNIT IV - PROPERTIES OF CONTEXT FREE LANGUAGES

Simplification of CFG

T1- Ch3.7.1,R1-Ch7

1

BB

Greibach Normal form

T1-Ch3.8.2,R2-Ch8

1

BB

Chomsky normal form

T1-Ch3.8.1,R1Ch7.1.5

1

BB

pumping lemma for CFL

T1- Ch4.7,R1-Ch7.2

2

BB

problems based on pumping Lemma

T1- Ch4.7,R1-Ch7.2

1

BB

Definitions of Turing machines

T1- Ch5.1,R2-Ch10

1

BB

1

BB

1

BB

2

BB

1

PPT

Techniques for Turing machine T1- Ch5.3, R1-Ch8.3 construction Revision UNIT –V UNDECIDABILITY Unsolvable Problems and T1- Ch6.1 Computable Functions Recursive and recursively enumerable languages

T1- Ch6.3,R19.2.2,Web resource

Undecidable problems with Turing Machine Tractable and Intractable problems Tractable and possibly intractable problems P and NP completeness Post Correspondence Problem Revision Total Revision Total

T1- Ch6.4,R1-9.2.3 T1- Ch6.6,R1Ch10.1,Web resource T1- Ch6.6,R1Ch10.1,Web resource T1- Ch6.7,R1Ch10.2,Web resource T1- Ch6.8,R1Ch10.1.5,Web resource

1

BB

2

BB

1

PPT

2

BB

2

BB

1

BB 49 2 51

CS8501 THEORY OF COMPUTATION

LTPC 3003

OBJECTIVES:  To understand the language hierarchy  To construct automata for any given pattern and find its equivalent regular expressions  To design a context free grammar for any given language  To understand Turing machines and their capability  To understand undecidable problems and NP class problems UNIT I AUTOMATA FUNDAMENTALS 9 Introduction to formal proof – Additional forms of Proof – Inductive Proofs –Finite Automata – Deterministic Finite Automata – Non-deterministic Finite Automata – Finite Automata with Epsilon Transitions UNIT II REGULAR EXPRESSIONS AND LANGUAGES 9 Regular Expressions – FA and Regular Expressions – Proving Languages not to be regular – Closure Properties of Regular Languages – Equivalence and Minimization of Automata. UNIT III CONTEXT FREE GRAMMAR AND LANGUAGES 9 CFG – Parse Trees – Ambiguity in Grammars and Languages – Definition of the Pushdown Automata – Languages of a Pushdown Automata – Equivalence of Pushdown Automata and CFG, Deterministic Pushdown Automata. UNIT IV PROPERTIES OF CONTEXT FREE LANGUAGES 9 Normal Forms for CFG – Pumping Lemma for CFL – Closure Properties of CFL – Turing Machines – Programming Techniques for TM. UNIT V UNDECIDABILITY 9 Non Recursive Enumerable (RE) Language – Undecidable Problem with RE – Undecidable Problems about TM – Post‘s Correspondence Problem, The Class P and NP. TOTAL :45 PERIODS OUTCOMES: Upon completion of the course, the students will be able to:  Construct automata, regular expression for any pattern.  Write Context free grammar for any construct.  Design Turing machines for any language.  Propose computation solutions using Turing machines.  Derive whether a problem is decidable or not. TEXT BOOK: 1. J.E.Hopcroft, R.Motwani and J.D Ullman, ―Introduction to Automata Theory, Languages and Computations‖, Second Edition, Pearson Education, 2003. REFERENCES: 1. H.R.Lewis and C.H.Papadimitriou, ―Elements of the theory of Computation‖, Second Edition, PHI, 2003. 2. J.Martin, ―Introduction to Languages and the Theory of Computation‖, Third Edition, TMH, 2003. 3. Micheal Sipser, ―Introduction of the Theory and Computation‖, Thomson Brokecole, 1997.

UNIT-I FINITE AUTOMATA

1.1 INTRODUCTION TO COMPUTATION  Computation is a general term for any type of information processing.  It is a process following a well defined model that is understood and can be expressed in an algorithm, protocol network topology etc.,

 It is also a major subject matter of computer science, it investigates what can or cannot be done in a computational manner. 1.1.1 Classes of Computation Computation can be classified as follows: 

Digital Vs Analog



Sequential Vs Parallel Vs Concurrent



Batch Vs interactive



Computation as Physical Phenomenon:

A computation can be seen as a purely physical phenomenon occurring inside a closed “physical system” called a computer. Examples of such physical system includes 

Digital Computers



Quantum Computers



DNA Computers



Molecular Computers



Analog Computers

1.1.2 Mathematical model of Computation In the theory of Computation, a diversity of mathematical models of computers has been developed. Typical mathematical models of computers are the following:

1. State models including a. Turing Machine b. Pushdown automata c. Finite Automaton 2. Functional models including 1

a. Lambda calculus 3. Logical models including a. Logic programming 4. Concurrent models including a. Actor model 1.1.3 Definition of Automata An open-ended computer science discipline that concerns an abstract device called an automaton, which performs a specific and recognition function. A formal system that represents a machine that acts according to given specification. 1.1.4 Alphabets, Strings, and Languages 1.1.4.1 Alphabets An alphabet is a finite, non-empty set of symbols. It is denoted by ∑. Example:

i.

∑ = {a, b}, an alphabet of 2 symbols a and b.

ii.

∑ = {0, 1, 2}, an alphabet of 3 symbols 0,1 and 2.

1.1.4.2 Strings A string or word over an alphabet ∑ is a finite sequence of symbols from ∑. Example: i

If ∑ = {a, b}, then abab, aabba, aaabba are all strings over the alphabet ∑ = {a, b}.

ii

If ∑ = {a}, then a, aa, aaa are all strings over the alphabet ∑ = {a}.

1.1.4.3 Languages For any alphabet ∑, any aubset L of ∑* is a language, a set of strings from an alphabet is called as a ‘Language’. Example:

i.

English: It is a Language over ∑ = {a, b, c, …, z}.

ii.

Binary String: {0,1,01,10,0101,…} is a language over ∑ = {0, 1}.

iii. If ∑ = {a, b} is an alphabet then ∑* = { є, a, b, aa, ab, … } is a language.

2

1.2 INTRODUCTION TO FORMAL PROOF DEFINITION A proof of a statement is essentially just a convincing or justifying argument that the statement is true. A proof not only convinces but explains why the statement is true and also how it relates to other statements and how it fits into the overall theory. There are two types of proofs:

1. Deductive proof 2. Inductive proof 1.2.1 Deductive Proof A deductive proof consists of a sequence of statements whose truth leads us from some initial statement called hypothesis or given statements to a conclusion statement. The theorem that is proved when we go from a hypothesis H to a conclusion C is the statement “if H then C”, we say that “C is deduced from H”. Theorem 1: If x≥4 then 2x ≥x2. Proof: Here Hypothesis H is x≥4 Conclusion C is 2x ≥x2 x≥4:

 Hypothesis has a parameter x and it is neither true nor false.  The truth depends on the value of the parameter i.e) h is true for x=6 and false for x=2. 2x ≥x2: The conclusion C is 2x ≥x2. This statement also uses parameter x and is true for certain values of x and not for others. Example:

 C is false for x=3 since 23=8 which is not as large as 3*2=9 (8 ≥ 9).  C is true for x=4 since 24=4*2=16.  For x=5. The statement is also true since 25=32 is at least as large as 5*2=25 (32 ≥ 25).

 Let us conclude the conclusion as 2x ≥x2 will be true whenever x≥4.

3

1.2.2 Modus ponens

 The hypothesis of some theorem is a previous statement, then the conclusion of that theorem is true, and can be written down as a statement of our proof. This logical rule is called modus ponens.

 If we know that H is true, and we know “if H then C” is true, we may conclude that C is true. Proof: The intuitive argument that tells the conclusion 2x ≥x2 is true for the hypothesis x ≥ 4. If the hypothesis is true for x, that is, x is the sum of the squares of four integers, then x must be at least 4. Statement

Justification

1. x=a2+b2+c2+d2

Given

2. a≥1,b≥1,c≥1,d≥1

Given

3. a2≥1,b2≥1,c2≥1,d2≥1

Follows statement 2

4. x ≥ 4

Follows statement 1 and 3

5. 2x ≥x2

Follows statement 4

Step 1: Let a, b, c and d is the names of the four integers. One of the given statements of the theorem says x is the sum of the squares of four integers. Step 2: This statement represents four distinct statements, one of the four integers involved. Each values being squared must be at least 1. Step 3: We observe that if a number is at least 1 then its square also at least 1. Step 4: It uses the statements 1 and 3 using well known properties of arithmetic; we conclude that x is at least 1+1+1+1 or 4. Step 5: In the final step, we use the statement 4. Theorem 1 is the justification for writing down its conclusion since its hypothesis is a previous statement.

4

For Example Prove that root 2 is not a rational The proof requires these facts about integers (which are the whole numbers, 0, 1, -1, 2, 2, 3, -3, etc.). 1. For integers a, if a2 is even, then a is even. The definition of even is that c is even if and only if there is some integer k such that c=2*k. 2. For integers a, if a 2 is odd, then a is odd. The definition of odd is that c is not even; necessarily, this means that there is some integer k such that c=2*k+1. 3. If a number x is the ratio of two integers, then it is the ratio of two relatively prime integers. That is, if x is a ratio of two integers, then there are some integers a and b such that b is not 0, x=a/b, and the greatest common divisor of a and b is 1 (1 and -1 both divide a and b, but no other integers do that). Suppose that x is the square root of 2 and that x is also the ratio of two integers. Let a and be b relatively prime integers such that b is not 0 and x=a/b. Then 2=x2=(a2)/(b2). So, 2 * (b2)= a2. Therefore, a2 is even (because it is twice another integer). By (1) above, a is even. Thus a=2*k for some integer k, and hence 2 * (b2)= (2k)2 Therefore, 2 * (b2)= 4*(k2). Divide by two, to discover that b2= 2*(k2). Therefore b2 is even (because it is twice another integer). By (1) above, b is even. Therefore, b=2*j for some integer k. Therefore, a and b are not relatively prime, because each has 2 as a divisor and 2 is bigger than 1 (their supposed greatest common divisor). This is a contradiction. The contradiction means that something in our "Suppose that x is the square root of 2 and x is also the ratio of two integers" is false. So, if one part of this "and" sentence is true, the other part must be false. In particular, if x is indeed the square root of 2, then x is NOT the ratio of two integers. In mathematical terminology, x is irrational. "Ir" as a prefix means "not". So x is NOT rational where rational means being the ratio of two integers (with the denominator integer non-zero)

5

1.3 ADDITIONAL FORMS OF PROOF 

Proofs about sets



Proofs by contradiction



Proofs by counter example



Proofs by Contrapositive

1.3.1 Proof by Contrapositive: The contrapositive of a conditional statements is formed by negating both the hypothesis and the conclusion and then interchanging the resulting negations. Ex:

p→q

Contrapositive is ‫ך‬q → ‫ך‬p In other words, it does both the jobs inverse and converse. Theorem: Conditional: For any real numbers a, b, if ab=0 then either a=0 or b=0. Contrapositive: For any real numbers a, b, if a is not 0 and b is not 0, then ab is not 0. 1.3.2 Proof by Contradiction “H and not C implies falsehood”

 That is start by assuming both the hypothesis H and the negation of the conclusion C

 Complete the proof by showing that something known to be false follows logically from H to not C. This form of proof is called as proof by contradiction. Theorem: To prove for any sets A, B, and C if A∩B = ϕ and C subset B and A∩C ≠ ϕ. Therefore there exists x with x Є A∩C, then x Є A and x Є C.

 Since C subset B and x Є C, it follows that x Є B.  Therefore x Є A∩B which contradicts the assumption that A∩B =ϕ  Since the

assumption that

the

conditional

statement

false leads to a contradiction, the statement is proved.

6

is

1.3.3 Proof by Counter Example In order to prove certain statement, we need to see all possible conditions in which that statement remains rue. There are some situations n which the statement cannot be true. Theorem: There is no such pair of integers such that a mod b = b mod a. Proof: Consider a=2 and b=3, then clearly 2 mod 3 ≠ 3 mod 2.

 Thus the given pairs is true for any pairs of integers but if a=b then naturally a mod b = b mod a.

 Thus we need to change the statement slightly, we can say a mod b = b mod a when a = b. 1.3.4 Proof about Sets If E and F are two expressions representing sets, the statement E=F means that the two sets represented are the same. Example 1: The commutative law of union says that we can take the union of two sets R and S in either order. 

That is R∪S=S∪R



In this case E is the expression R∪S and F is the expression S∪R.



The commutative law of union says that E = F. Example 2:

“if and only

if statement” 

An element x is in E if and only if x is in F.



The form of any if and only if proof are as follows:



Proof that “ if x is in E, then x is in F”



Proof that if x is in F, then x is in E”

Theorem: (Let us prove the distributive law of union over intersection) R∪(S∩T)=(R∪S) ∩ (R∪T)

7

Proof: The two set expressions involved are E= R∪(S∩T) and F=(R∪S) ∩ (R∪T) In the ‘if’ part we assume element x is in E and show it is in F. Steps in ‘if part’ are as follows: Step

Statement

Justification

No. 1

x is in R∪(S∩T)

Given

2

x is in R or x is in S∩T

(1) and definition of union

3

x is in R or x is in S and T

(2) and definition of intersection

4

x is in R∪S

(3) and definition of union

5

x is in R∪T

(3) and definition of union

6

x is in (R∪S) ∩ (R∪T)

(4), (5) and definition of intersection

Steps in ‘only if part’ are as follows: Step

Statement

Justification

No. 1

x is in (R∪S) ∩ (R∪T)

Given

2

x is in R∪S

(1) and definition of intersection.

3

x is in R∪T

(1) and definition of intersection.

4

x is in R or x is in S and T

(2), (3) and reasoning about unions.

5

x is in R or x is in S∩T

(4) and definition of intersection.

6

x is in R∪(S∩T)

(5) and definition of union.

Since we have now proved both parts of the if-and-only-if statement, the distributive law of union over intersection is proved. 1.4 INDUCTIVE PROOFS:

 There is a special form of proof called inductive ie) essential when dealing with recursively defined objects.

8

 Many of the most familiar inductive proofs deals with integers, but in automata theory we also need inductive proofs about such recursively defined concepts as trees and expression of various sorts such as regular expressions. 1.4.1 Mathematical Induction Mathematical induction is a way of establishing the correctness of formulas involving an integer variable. ...