Theory Of Computation by Dr Amol Prakash Bhagat

Machines and Models

What you'll learn

Construction of finite state machines to solve problems in computing

Regular expressions for the formal languages

Construct and analyze Push Down, Turing Machine, Linear Bounded Automata for formal languages

Understanding of the Chomsky Hierarchy

Decidability and un-decidability problems

Requirements

No experience needed. You will learn everything you need to know.

Description

Finite State Machines: Alphabet, String, Formal and Natural Language, Operations, Definition and Design DFA (Deterministic Finite Automata), NFA (Non Deterministic Finite Automata), Equivalence of NFA and DFA: Conversion of NFA into DFA, Conversion of NFA with epsilon moves to NFA, Minimization of DFA, Definition and Construction of Moore and Mealy Machines, Inter-conversion between Moore and Mealy Machines. Minimization of Finite Automata. (Construction of Minimum Automaton)Regular Expression and Regular Grammar: Definition and Identities of Regular Expressions, Construction of Regular Expression of the given Language, Construction of Language from the RE, Conversion of FA to RE using Arden’s Theorem, Inter-conversion RE to FA, Pumping Lemma for RL, Closure properties of RLs, Regular grammar, Equivalence of RG ( RLG and LLG) and FAContext Free Grammar and Languages: Introduction, Formal Definition of Grammar, Notations, Derivation Process: Leftmost Derivation, Rightmost Derivation, Derivation Trees, Construction of Context-Free Grammars and Languages, Pumping Lemma for CFL, Simplification of CFG, Normal Forms (CNF and GNF), Chomsky HierarchyPushdown Automata: Introduction and Definition of PDA, Construction of PDA, Acceptance of CFL, Equivalence of CFL and PDA: Inter-conversion , Introduction of DCFL and DPDA, Enumeration of properties of CFL, Context Sensitive Language, Linear Bounded AutomataTuring Machines: Formal definition of a Turing Machine, Design of TM, Computable Functions, Church’s hypothesis, Counter machine, Variants of Turing Machines: Multi-tape Turing machines, Universal Turing MachineDecidability and Un-Decidability: Decidability of Problems, Halting Problem of TM, Un-Decidability: Recursive enumerable language, Properties of recursive & non-recursive enumerable languages, Post Correspondence Problem, Introduction to Recursive Function Theory

Overview

Section 1: Finite State Machines

Lecture 1 Introduction

Lecture 2 Theory of Computation, Alphabets, Strings, Languages

Lecture 3 Operations

Lecture 4 Finite Automaton

Lecture 5 A 4 bit shift register as finite state machine

Lecture 6 Block Diagram of a Finite Automaton

Lecture 7 Description of Finite Automaton

Lecture 8 String Processing by Finite Automaton

Lecture 9 Language of a Finite Automaton

Lecture 10 Examples - String Acceptability and Language of a Finite Automaton

Lecture 11 Deterministic and Nondeterministic Finite Automata, DFA, NFA, NDFA

Lecture 12 Acceptance of String by Nondeterministic Finite Automata, NFA, NDFA

Lecture 13 Converting NFA to DFA

Lecture 14 Construction of a Finite Automaton

Lecture 15 Finite Automata with Outputs, Moore Machine, Mealy Machine

Lecture 16 Conversion of Moore Machine to Equivalent Mealy Machine

Lecture 17 Conversion of Mealy Machine to Equivalent Moore Machine

Lecture 18 Minimization of Finite Automata

Lecture 19 Example - Minimization of Finite Automata

Lecture 20 Section 1: Practice Examples

Section 2: Regular Expression and Regular Grammar

Lecture 21 Regular Expression, Regular Set, Regular Language, Finite Automata

Lecture 22 Correspondence between Regular Expression and Regular Set

Lecture 23 Example: Correspondence between Regular Expression and Regular Set

Lecture 24 Examples: Regular Expression for Regular Set or Regular Language

Lecture 25 Examples: Regular Expression for Regular Set or Regular Language

Lecture 26 Examples: Regular Expression, Regular Set, Regular Language

Lecture 27 Examples: Finite Automaton Corresponding to given Regular Expression

Lecture 28 Transition System Containing Ԑ- Moves

Lecture 29 Eliminating Ԑ- Moves

Lecture 30 Arden's Theorem

Lecture 31 Arden's Theorem: Finding Regular Expression from Finite Automaton

Lecture 32 Equivalence of Two Finite Automata

Lecture 33 Example: Equivalence of Two Finite Automata

Lecture 34 Closure Properties of Regular Languages

Lecture 35 Finite Automaton for Concatenation of Languages

Lecture 36 Finite Automaton for Transpose of a Language and Reverse of a Language

Lecture 37 Finite Automaton for Complement of a Language

Lecture 38 Finite Automaton for Kleen's Star of a Language

Lecture 39 Regular Grammar, Construction of a Regular Grammar Generating L(M)

Lecture 40 Construction of a Transition System M Accepting L(G) for a given Regular Grammar

Lecture 41 Section 2: Practice Examples

Section 3: Context Free Grammar and Languages

Lecture 42 Context Free Grammars

Lecture 43 Derivation Trees, Context Free Grammars

Lecture 44 Leftmost Derivation, Rightmost Derivation, Derivation Trees

Lecture 45 Ambiguity in Context Free Grammars, Ambiguous Context Free Grammar

Lecture 46 Designing Context Free Grammar for the given Language

Lecture 47 Chomsky Classification of Grammar

Lecture 48 Construction of Reduced Grammars: Part 1

Lecture 49 Construction of Reduced Grammars: Part 2

Lecture 50 Construction of Reduced Grammars: Part 3

Lecture 51 Elimination of Null Productions

Lecture 52 Elimination of Unit Productions from Context Free Grammar

Lecture 53 Reduction to Chomsky Normal Form

Lecture 54 Greibach Normal Form

Lecture 55 Section 3: Practice Examples

Section 4: Pushdown Automata

Lecture 56 Designing Pushdown Automata for given Context Free Language

Lecture 57 Examples on Push Down Automata

Lecture 58 Obtaining PDA from CFG

Lecture 59 Obtaining Context Free Grammar from Pushdown Automata

Lecture 60 GATE Questions

Lecture 61 Section 4: Practice Examples

Section 5: Turing Machines

Lecture 62 Turing Machine, Turing Machine Model, String Processing in Turing Machine

Lecture 63 Designing a Turing Machine for given Language

Lecture 64 Designing Turing Machine for Given Language

Lecture 65 Designing Turing Machine for Given Language

Lecture 66 Designing a Turing Machine

Lecture 67 Linear Bounded Automata, Model of Linear Bounded Automata

Lecture 68 Obtaining Grammar for Turing Machine, Obtaining Grammar for LBA

Lecture 69 Section 5: Practice Examples

Section 6: Decidability and Un-Decidability

Lecture 70 Recursive and Non Recursive Languages

Lecture 71 Post Correspondence Problem, PCP, Finding whether the PCP has a solution

Lecture 72 Primitive Recursive Functions, Recursive Function Theory, Initial Functions

Lecture 73 Section 6: Practice Examples

Undergraduate and Post Graduate Students