Theory of Computation Notes | B.Sc. (Computer Science) Semester 3 | Mumbai University | munotes

Contents

Module I Introduction to Theory of Computation, Automata Theory, Formal Languages, Regular Languages and Context Free Languages

1. What This Subject Is About, and the Four Questions It Answers 1
2. Sets: The Vocabulary Everything Else Is Written In 6
3. Alphabets, Strings and Languages 11
4. Relations, and the Equivalence Relation That Runs Through This Subject 16
5. Functions: What the Transition Function Actually Is 21
6. Proof Techniques: Five Ways to Be Sure 25
7. Counting the Uncountable: Diagonalisation, and Why Some Languages Have No Machine 30
8. What an Automaton Is 35
9. The Deterministic Finite Automaton, Formally 40
10. Transitions and Their Properties: the Function, the Table and the Diagram 44
11. The Extended Transition Function: What a Machine Does to a Whole String 49
12. Acceptability: When a Machine Accepts a String, and What Language It Accepts 53
13. Designing a DFA: the Method, and Eight Machines Built With It 58
14. Nondeterminism, and the Nondeterministic Finite Automaton 64
15. Empty Moves, and the Epsilon Closure 69
16. DFA and NDFA Equivalence: the Subset Construction 74
17. Removing the Empty Moves 80
18. Mealy and Moore Machines: a Machine That Writes 84
19. Converting a Moore Machine to a Mealy Machine, and Back 88
20. Minimizing Automata: the Partition Method 93
21. The Myhill Nerode Theorem, and a Second Way to Prove a Language Not Regular 99
22. What a Grammar Is 105
23. Derivations: How a Grammar Makes a String 110
24. The Language Generated by a Grammar, and Proving It Is the One You Claim 115
25. Writing a Grammar for a Language You Are Given 120
26. The Chomsky Classification of Grammars and Languages 126
27. Recursive and Recursively Enumerable Sets 132
28. Operations on Languages 137
29. Languages and Automata: Which Machine Goes With Which Grammar 144
30. Regular Grammar: the Right Linear and Left Linear Forms 149
31. Regular Expressions 154
32. The Identities of Regular Expressions 159
33. Writing a Regular Expression for a Language You Are Given 164
34. From a Regular Expression to a Finite Automaton 170
35. From a Finite Automaton to a Regular Expression: Arden's Theorem and State Elimination 175
36. The Pumping Lemma for Regular Languages 181
37. Applications of the Pumping Lemma 187
38. Closure Properties of the Regular Languages 193
39. The Decision Problems of the Regular Languages 199
40. Regular Sets and Regular Grammar: Kleene's Theorem Assembled 204
41. Context Free Grammars and Context Free Languages 209
42. The Derivation Tree 214
43. Leftmost and Rightmost Derivations 219
44. Ambiguity of a Grammar 223
45. Simplifying a Grammar, One: Useless Symbols 228
46. Simplifying a Grammar, Two: Null Productions 233
47. Simplifying a Grammar, Three: Unit Productions, and the Reduced Grammar 238
48. Chomsky Normal Form 243
49. Greibach Normal Form 248
50. The Pumping Lemma for Context Free Languages 254
51. Closure Properties and Decision Problems of the Context Free Languages 261

Module II Pushdown Automata, Linear Bound Automata, Turing Machines, and Computability and Complexity

1. The Pushdown Automaton 268
2. Instantaneous Descriptions and Moves 274
3. Acceptance by a PDA: by Final State and by Empty Stack 279
4. Designing a PDA: the Balanced Languages 284
5. Designing a PDA: Palindromes, and Counting Two Things at Once 289
6. The Deterministic Pushdown Automaton 295
7. From a Context Free Grammar to a Pushdown Automaton 300
8. From a Pushdown Automaton to a Context Free Grammar 305
9. The Linear Bounded Automaton Model 310
10. Linear Bounded Automata and the Context Sensitive Languages 315
11. The Turing Machine 320
12. Representations of a Turing Machine 325
13. Acceptability by a Turing Machine: Accept, Reject and Loop 330
14. Designing and Describing a Turing Machine 335
15. Turing Machine Construction: Machines That Recognise 340
16. Turing Machine Construction: Machines That Compute 345
17. Variants of the Turing Machine: More Tapes, More Tracks, More Heads 350
18. Variants of the Turing Machine: Nondeterministic, Offline, and the Enumerator 355
19. Recursive and Recursively Enumerable Languages 360
20. Decidable and Undecidable, and What the Complement Tells You 364
21. The Church Turing Thesis 368
22. The Universal Turing Machine 373
23. The Halting Problem 378
24. Reduction: Proving a Second Problem Unsolvable 383
25. Rice's Theorem 388
26. The Post Correspondence Problem, and the Undecidable Problems of Grammars 393
27. Time Complexity 398
28. Space Complexity 403
29. Big O Notation, and the Family Around It 408
30. Class P 413
31. Class NP, and the Certificate 418
32. Polynomial Reductions 423
33. NP Complete and NP Hard, and Cook's Theorem 429
34. Proving a Problem NP Complete: Three Reductions Worked 435
35. Complexity Hierarchies, and the P Against NP Question 441
36. The Machines and the Grammars, Side by Side 446