CS8501 - Theory OF Computation Question Bank with Answers PDF

Preview

Summary

CS8501 THEORY OF COMPUTATIONUNIT I AUTOMATA FUNDAMENTALSIntroduction to formal proof – Additional forms of Proof – Inductive Proofs –Finite Automata – Deterministic Finite Automata – Non-deterministic FiniteAutomata – Finite Automata with Epsilon TransitionsUNIT II REGULAR EXPRESSIONS AND LANGUAGESR...

Description

Visit for More : www.LearnEngineering.in

CS8501 THEORY OF COMPUTATION UNIT I AUTOMATA FUNDAMENTALS 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 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 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 Normal Forms for CFG – Pumping Lemma for CFL – Closure Properties of CFL – Turing Machines – Programming Techniques for TM. UNIT V UNDECIDABILITY Non Recursive Enumerable (RE) Language – Undecidable Problem with RE – Undecidable Problems about TM – Post‘s Correspondence Problem, The Class P and NP. TOTAL :45PERIODS 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.

Visit for More : www.LearnEngineering.in

Visit for More : www.LearnEngineering.in

Department of Computer Science and Engineering SUBJECT CODE: CS8 5 0 1 SUBJECT NAME: Theory Of Computation Regulation: 2017

Visit for More : www.LearnEngineering.in

Visit for More : www.LearnEngineering.in

TABLE OF CONTENTS Sl.no a. b. c. d. 1. 2. 3. 4. 5. 6. 7. e. f. 8. 9. 10. 11. 12. g. h. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24.

Topic Aim & Objective of the subject Detailed Lesson Plan Unit I- Introduction To Compilers Part A Part B Language Processor Software Tools used in Compilation Analysis Part of Compilation Phases Of Compiler Cousins Of Compiler The Grouping Of Phases Compiler Construction Tools Unit II- Lexical Analysis Part A Part B Need and Role of Lexical Analyzer Input Buffering Expressing Tokens by Regular Expressions Language for Specifying Lexical Analyzer Regular Expression to DFA Unit III- Syntax Analysis Part A Part B Need and Role of the Parser Various Terminologies in Parsing Context Free Grammars Writing a Grammar Recursive Descent Parser Predictive Parser Construction of Predictive Parsing Table Shift Reduce Parser LR Parser Construction of SLR Parsing Table Construction of LALR Parsing Table YACC-Design of a Syntax Analyzer Unit IV- Syntax Directed Translation & Runtime Environment

Page No 1 2 4 8 8 9 10 11 16 18 18 20 23 23 25 26 31 33 35 39 39 41 42 45 48 50 53 55 58 61 65 68

Visit for More : www.LearnEngineering.in

Visit for More : www.LearnEngineering.in

i. j. 25. 26. 27. 28. 29. 30. 31. 32. 33. k. l. 34. 35. 36. 37. 38. 39. 40. m. 41.

Part A Part B Source Language Issues Storage Organization Storage Allocation Type Systems Specification of a Simple Type Checker Syntax Directed Definition Construction of Syntax Tree Parameter Parsing Design of a Predictive Translator Unit V- Code Optimization and Code Generation Part A Part B Principal Sources of Optimization DAG Optimization of Basic Blocks Global Data Flow Analysis Issues in the Design of A Code Generator A simple Code Generator Algorithm Peephole Optimization Industrial / Practical Connectivity of the subject University Question papers

71 74 74 76 77 81 86 88 92 94 96 100 103 103 108 113 114 122 124 127 130

Visit for More : www.LearnEngineering.in

Visit for More : www.LearnEngineering.in

AIM AND OBJECTIVE OF THE SUBJECT

The student should be made to: 1. Understand various Computing models like Finite State Machine, Pushdown Automata, and Turing Machine. 2. Be aware of Decidability and Un-decidability of various problems. 3. Learn types of grammars.

1

Visit for More : www.LearnEngineering.in

Visit for More : www.LearnEngineering.in

DETAILED LESSON PLAN

TEXT BOOKS: 1. Hopcroft J.E., Motwani R. and Ullman J.D, “Introduction to Automata Theory, Languages and Computations”, Second Edition, Pearson Education, 2008. (UNIT 1,2,3) 2. John C Martin, “Introduction to Languages and the Theory of Computation”, Third Edition, Tata McGraw Hill Publishing Company, New Delhi, 2007. (UNIT 4,5) REFERENCES: 1. Mishra K L P and Chandrasekaran N, “Theory of Computer Science - Automata, Languages and Computation”, Third Edition, Prentice Hall of India, 2004. 2. Harry R Lewis and Christos H Papadimitriou, “Elements of the Theory of Computation”, Second Edition, Prentice Hall of India, Pearson Education, New Delhi, 2003. Sl. No

Unit

Topic / Portions to be Covered

Hours Required / Planned

Cumulative Hrs

1

Introduction- Basic Mathematical Notation and techniques

1

1

2

Finite State systems – Basic Definitions – Finite Automaton

1

2

1

3

1

4

1

5

DFA & NDFA – Finite Automaton with € - moves

3

Regular Languages- Regular Expression

4

Equivalence of NFA and DFA

5 6

Equivalence of NDFAs with and without €moves

1

6

7

Equivalence of finite Automaton and regular expressions

1

7

1

8

1

9

1

10

I

8 9 10

Minimization of DFA Pumping Lemma for Regular sets Problems based on Pumping Lemma.

Books Referred TI

T1 T1 T1 T1 T1

T1 T1 T1 T1

2

Visit for More : www.LearnEngineering.in

Visit for More : www.LearnEngineering.in

Sl. No

Unit

Topic / Portions to be Covered Grammar Introduction

11

Types of Grammar

12

Context Free Grammars and Languages

13

Hours Required / Planned

Cumulative Hrs

1

11

1

12

1

13

14

Derivations and Languages

1

14

15

Ambiguity- Relationship between derivation and derivation trees

1

15

1

16

1

17

1

18

1

19

1

20

II 16

Simplification of CFG Elimination of Useless symbols - Unit productions- Null productions

17

Greiback Normal form

18

Chomsky normal form

19

Problems related to CNF and GNF.

20 21

Pushdown Automata- Definitions

1

21

22

Moves – Instantaneous descriptions

1

22

1

23

4

27

2

29

1

30

1

31

1

32

Deterministic pushdown automata

23 III 24

Pumping lemma for CFL

25

Problems based on pumping Lemma.

26

Definitions of Turing machines

27 IV 28

Equivalence of Pushdown automata and CFL

Models

Books Referred T1 T1 T1 T1 T1 T1 T1 T1 T1 T1 T1 T1 T1 T1 T1 T1 T1 T1

3

Visit for More : www.LearnEngineering.in

Visit for More : www.LearnEngineering.in

Sl. No

Unit

Computable languages and functions

29

Techniques for Turing machine construction

30

Multi head and Multi tape Turing Machines

31

The Halting problem

32

Partial Solvability

33

Problems about Turing machine

34

Chomskian hierarchy of languages.

35

Unsolvable Problems and Computable Functions

36

Primitive recursive functions

37

Recursive and recursively enumerable languages

38

Universal Turing machine

39 40 41 42 43 44

Topic / Portions to be Covered

V

Measuring And Classifying Complexity Tractable and Intractable problems Tractable and possibly intractable problems P and NP completeness Polynomial time reductions

Hours Required / Planned

Cumulative Hrs

1

33

2

35

1

36

1

37

1

38

1

39

1

40

1

41

1

42

2

44

1

45

1

46

1

47

1

48

1

49

1

50

Books Referred T1 T1 T1 T1,T2 T1,T2 T1,T2 T1,T2 T1,T2 T1,T2 T1,T2 T1,T2 T1,T2 T1,T2 T1,T2 T1,T2 T1,T2

4

Visit for More : www.LearnEngineering.in

Visit for More : www.LearnEngineering.in

UNIT I- FINITE AUTOMATA Introduction- Basic Mathematical Notation and techniques- Finite State systems – Basic Definitions – Finite Automaton – DFA & NDFA – Finite Automaton with €- moves – 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.

PART-A 1. Define the following: a. Symbol A symbol is an abstract entity. Letters and digits are symbols. b. String: A string is a finite sequence of symbols. Eg: abc, dog are strings c. Language: A language is a set of strings of symbols from one alphabet. Ф, { ϵ} are languages. Alphabet: An alphabet is a finite set of symbols. 2. What is relation? A binary relation is a set of pairs. The first component of each pair is chosen from a set called the domain and the second component of each pair is chosen from a set called a range. What are the properties of relation? a. Reflexive: If aRa for all a in S b. Irreflexive: aRa is false for all a in S c. Transitive: aRb and bRc imply aRc d. Symmetric: aRb implies bRa e. Asymmetric: aRb implies that bRa is false 5

Visit for More : www.LearnEngineering.in

Visit for More : www.LearnEngineering.in

3. What is an equivalence relation? A relation R that is i. Reflexive ii. Symmetric iii. Transitive is said to be an equivalence relation. 4. What are the methods of formal proof? i. Deductive proof ii. Reduction to definition iii. Other theorem forms iv. Theorems that appear not to be if-then statements 5. What are the applications of theory of computation? i. Compiler design ii. Robotics iii. Artificial intelligence iv. Knowledge engineering 6. What is finite state system? Finite state system: The finite Automaton is a mathematical model of a system with discrete inputs and outputs. The system with discrete inputs and outputs. The system can be in any one of the finite number of internal states and input symbols. Input Tape

0

+

1

.

.

. tape head

Finite control

7. what is Deterministic Finite Automata(DFA)? DFA: DFA is defined by a 5 tuple. M=(Q,Σ,δ,q0 ,F) 6

Visit for More : www.LearnEngineering.in

Visit for More : www.LearnEngineering.in

Where Q- is a finite set of states Σ- is a finite input alphabet q0- in a q is a 9. Define Non deterministic finite automata (NFA) NFA : NFA is defined as 5 tuples M = (Q,Σ,δ,q0,F) Q-> Set of states Σ -> set of input symbols δ > is a transition function mapping from Qx Σ-> 2Q qo -> an initial state F -> set of final stater F- n , we can write z = uvw in such a way that |uv|- and for all i>0 uv i w is in L 15. Construct a DFA that accepts input string of0,s and 1’s that end with 11.

8

Visit for More : www.LearnEngineering.in

Visit for More : www.LearnEngineering.in

PART-B 1.A INTRODUCTION 1. Write short notes on Strings , Alpbhapets and Languages. Introduction Strings, Alphabets and Languages Symbol :  A symbol is abstract entity.  Letters and digits are examples of symbols. String :  A string or word is finite sequence of symbol.  Example a, b and c are symbols and abcd is a string.  The length of a string w is the number of symbols composing the string.  It is denoted as w  Example : abcd has length 4 The empty string E, the string consisting of zero symbols E =0.  A prefix of a string is any number of leading symbols of the string.  Example : String abc has prefixes, E, a, ab, abc.  A suffix is any number of trailing symbols of that string.  Example : String abc has suffixes E, c, bc, abc  A prefix or suffix of a string other than the string itself is called a proper prefix or suffix.  The concatenation of two strings is the string formed by writing the first followed by the second without space.  For eg.  Concatenation of dog and house is doghouse  The empty string is the identity for concatenation operator  w  w  w Alphabet :  An alphabet is a finite set of symbols. Language : 9

Visit for More : www.LearnEngineering.in

Visit for More : www.LearnEngineering.in

 A language is a set of string of symbols from some one alphabet.  The empty set φ and the set consisting of the empty string  are languages.  The set of all string over a fixed alphabet  , this language is denoted by  *  Example 1.  a * , a,aa,aaa,...

2.   0,1 * , 0,1, 01,10 , 00 ,11, 000 , 000 , ...

Set Notation :  Set is a collection of objects without repetition.  Finite sets may be specified by two forms i. listing their members between brachets. ii. Set former

x | p x  x in A | p x   If every member of A is a member of B, then we write A B and say A is contained in B.  If A B but A B , that is every member of A is in B and there is same member of B that is not in A, then we write A B .  A and B are equal if they have same members That is A = B iff A B nad B A . Operations on Sets : 1. A  B , the union of A and B is

x| x is in A of x is in B 2. A  B , the intersection of A and B is

x | x is in A and x is in B 3. A – B, the difference of A and B is

x| x is in A and x is not in B

4. A x B, the Cartesian product of A and B, is the set of ordered pairs (a, b) such that a is in A and b is in B. 5. 2A , is the power set of A is the set of all, subsets of A Example : Let A = {1, 2} B = {2, 3} 1. A  B = {1, 2, 3} 10

Visit for More : www.LearnEngineering.in

Visit for More : www.LearnEngineering.in

2.

A  B = {2}

3. A – B = {1} 4. A x B = {(1, 2), (1, 3), (2, 2), (2, 3)} 5. 2 = 1,2,1, 2 A

 If A and B have n and m members respectively, then A x B has nm members 2A has 2n members. Relations :  A binary relation is a set of pairs.  The first component of each pair is chosen from a set called the domain and the second component of each pair is chosen from a set called a range.  If R is a relation and (a, b) is a pair in R then we write a R b. Properties of Relations :  We say a relation R on set S is 1. Reflexive if aRa for all a in S 2. Irreflexive if aRa is false for all a in S 3. Transitive if aRb and bRc imply aRc 4. Symmetric if aRb implies bRa 5. Asymmetic if aRb implies that bRa is false.  Any asymmetric relation must be irreflexive. Equivalence relation :  A relation R that is i. Reflexive ii. Symmetric iii. Transitive is said be an equivalence relation. Closure of relations :  The transitive closure of R, denoted Rt is defined by 1) If (a, b) is in R, then (a, b) is in R+ 2) if (a, b) is in Rt and (b, c) is in R then (a, c) is in R+ 3) Nothing is in R+, unless it follows from (1) and (2) 11

Visit for More : www.LearnEngineering.in

Visit for More : www.LearnEngineering.in

 The reflexive and transitive closure of R denoted R+ is defined as R+ U a , a | a is in s Example : Let R = {(1, 2), (2, 2), (2, 3)} be a relation on the set {1, 2, 3} R+ = {(1, 2), (2, 2) (2, 3), (1, 3)} R* = {(1, 2), (2, 2), (2, 3), (1, 3), (1, 1) (3, 3)} Graphs :  A graph consist of a finite set of verticles V and a set of paris of vertices E called edges.  Graph is denoted as G = (V, E)  A path in a graph is a sequence of verticle V1, V2, V3, …., Vk k 1, such that there is an edge (Vi, Vi+1) for each I | i  k Directed Graphs:  A directed graph or digraph consists of a finite set of vertices V and a set of ordered pairs of vertices E called arcs.  The arc from V  W is denoted as V  W  If V  W is an arc, we say V  Pr edecessorof W W  Successorof V Trees:  A tree is a digraph with the following properties 1. Three is one vertex, called the root that has no predecessor and from which there is a path to every vertex. 2. Each vertex other than the root has exactly one predecessor. 3. The successor of each vertex is ordered from the left.  If there is a path from vertex V1 to Vertex V2 then V2 is said to be descendant of V1 and V1 is said to be an ancestor of V2. 1.B INTRODUCTION TO FORMAL PROOF  Explain the four ways of Theorem Proving.  Explain the methods of Formal Proof Introduction to formal Proof :  Formal proof is a step by step to solve the problem. 12

Visit for More : www.LearnEngineering.in

Visit for More : www.LearnEngineering.in

 In format proof We try to prove that statement B is true because statement A is true.  The statement A is called hypothesis and B is called conclusion statement. The four ways of Theorem Proving (or) Methods of formal proof. (1) Deductive Proof (2) Reduction Proof (3) Other theorem forms (4) Theorems that appear not to be if then statement. Deductive Proof :  A deductive proof consists of a sequence of statements whose truth leads us from some initial statement called the hypothesis or the given statement (s) 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 deducted from H  The hypothesis may be true or false hypically depending on values of its parameters. Theorem 1 If x  4 then 2 x  x 2 Proof :  The hypothesis H is x  4  The hypothesis has a parameter x and thus is neither true of false.  eg. H is true for x = 6 and false x = 2  The conclusion C is 2 x  x 2  This statement also uses parameter x and is true for certain values of x and not others.  The intuitive argument that tells the conclusion 2 x  x 2 will be true whenever x  4  The left side 2x doubles each time x increase by 1 2

 x 1   The right side x2 grows by the ration    x   Hence if x  4 then 2 x  x 2 , for all integers x ie 2 x  x 2 is deducedfrom x  4

Theorem 2 : 13

Visit for More : www.LearnEngineering.in

Visit for More : www.LearnEngineering.in

If x is the sum...