Introduction to Toc, Computability Theory, Real Number System, Rational Functions, Set Theory, Tuple, Logic, Propositions, Quantifiers, Relations, Domains & Range, Congruence Relation, Partition, R-Relative Set, Equivalence relations & partitions, Congruence relations and equivalence classes, Functions, Types & Compositions, Proof by Contrapositive, Proof by Contradiction, Principle of Mathematical Induction, Recursive functions and proof by Induction, Finite Automata, Alphabets, Strings & Languages, Determinism & Non-Determinism, Introduction to Computation, Finite State Machines - some examples, Extended Transition Function, Distinguishing one state from another, Regular Languages and Regular Expressions over Sigma, Unions, Intersections and Complements of Finite State Machines, NFA (Non-Deterministic Finite Automata), Recursive & Non-Recursive definitions of NFA, Acceptance by NFA, NFA with Lambda transitions, Equivalence of NFA & NFA_Lambda, Converting NFA_Lambda to DFA.
Regular Languages, Kleene's Theorem, Criterion for Regularity, Myhill Nerode Theorem, Strings with second-last symbol '0'. DFA which represents the strings ending with 1 and not containing '00', Palindromes over the alphabet {a, b}, Minimal Final Automata, Lemma, Algorithms for identifying the pairs (p, q) with 'p' non_congruent to 'q', Problems - to find min-state DFA, Interpreting Myhil Nerode, Pumping lemma for regular languages, Problems using Pumping lemma, Weaker form of Pumping lemma for regular languages, Even weaker form of Pumping lemma, Problems, Context Free Languages (CFLs) & Push Down Automata (PDA), Definitions of CFL & CFG. Problems, Finding regular expressions corresponding to an automaton. Theorem: CFL - L1_Union_L2, L1_intersection_L2, L1_minus_L2, Grammar generating L1_concatenation_L2, Corollary: Every regular language is a CFL, Finding CFGs corresponding to regular languages, Regular grammars, problems, Power Set, Bell Number, Bell triangle, Theorem: General form of a regular grammar, Derivation trees & Ambiguity, Dangling 'Else', Unambiguous CFGs for regular expressions, Simplified forms & Normal forms, Nullable variables, Algorithm to find equivalent CFG with no Lambda productions, Elimination Unit Productions, Chomsky Normal From (CNF), problems, Syntax Diagrams, Problems, Push Down Automata, Acceptance by PDA, Deterministic PDA, Top-Down PDA corresponding to a CFG, A CFG corresponding to a given PDA, Backus Naur Form (BNF), Two Level Grammars, Van Wijngaarden Grammar, Problems, Ambiguity.
CFG corresponding to a given PDA, Theorem: There is a PDA corresponding to every CFG, Problems: CFG -> PDA, Parsing, Top-Down parser for balanced string of parenthesis, Eliminating Left Recursion, Factoring in CFG, Problems, LL Parser, First & Follow Set, Problems, Prefix Grammar, Live, Usable, Reachable & Useless Variables, Pumping Lemma for CFGs, Problems, KMP String Comparator, Problems: Finding REs, other problems, Graph representations, Problems on FAs, Closure properties of CFGs,Problems, GNF - Greibach Normal Form, Problems, CYK Algorithm, Simple Grammar, Problems on CFGs, Turing Machines, Acceptance by TMs, Examples, TM accepting Palindromes, TM accepting {ss | s is an element of {a, b}*}, TMs as Transducers, Definition: TM computing a function, TM computing a numerical function, TM that reverses a given string, TM to compute (N mod 2), TM to copy a string.
Construct a Turing Machine to delete a symbol, Construct a Turing Machine to insert a symbol, Implement a TM to Add 2 numbers, Implement a TM for subtraction operation, Combining Turing Machines, Accepting a palindrome using a composite TM, The characteristic function implementation using a TM, Problem, Turing Thesis, Variations of Turing Machines, Multiple Turing Machines, Theorem + Problems, Offline Turing Machines, Multidimensional Turing Machines, A simple TM to compute 'double', A Non_Deterministic Turing Machine, Problems, Theorem, A Universal Turing Machine, examples, Church Turing Thesis, Recursively Enumerable & Recursive languages, Recursive Functions, Computable function, Countable Set, "Let S be an infinite countable set, then its power-set 2^S is not countable", George Cantor, True or False & other problems, Injection function (One_One), Bijection function, Surjection function (Onto), Aleph_Null, Theorem: "Let S' be an infinite countable set, then its power-set 2^S is not countable", Theorem: "For any non-empty Sigma, there exists languages that are not recursively enumerable", Digress: George Ferdinand Ludwig Cantor (1845 - 1918), The Continuum, Cardinal Numbers, Bit_Torrent Protocol.
Theory of Computation
Last Updated: Feb 2019