Introduction To Automata Theory, Languages And Computation

Theory of computation, Automata Theory, Formal Language and Automata Theory

What you'll learn

Understand the basics of Automata Theory, Languages and its need

Understand the working of Finite Automata, Push Down Automata and Turing Machine

Able to solve problems using Finite Automata, Push Down Automata and Turing Machine

Able to recognize the relationship between various Automata

Understand the need for proving various equivalence between Automata

Requirements

No prerequisites are there for this course. Students can listen to the lectures to understand Automata Theory concepts from base.

Description

The aim of this course “Introduction to Automata Theory, Languages and Computation” is to give a detailed working explanation regarding each Mathematical model, its corresponding languages, and their provable equivalence. “Theory of Computation” has three major subdivisions namely1) Automata Theory2) Computability Theory3) Complexity TheoryThe automata theory deals with some Mathematical models that perform some operations automatically like programming machines. There are four main Mathematical models namely, Finite Automata(FA), Push Down Automata(PDA), Linear Bound Automata(LBA), and Turing Machine(TM). Each Mathematical model differs based on its memory units as FA has no external memory unit, PDA has stack as a memory unit, LBA has finite length tape as a memory unit and TM has infinite tape as a memory unit.Based on the limitations in the memory unit each model solves a limited set of problems only. The set of problems solved by each model is grouped as languages accepted by the model. The problems solved by Finite Automata are called Regular Language and its corresponding language representation is called Regular Grammar. The language accepted by Push Down Automata is called Context Free Language, the language accepted by Linear Bound Automata is called Context Sensitive Language, and the language accepted by Turing Machine is called Un-Restricted language since Turing machines have unlimited memory and random access to the memory unit.Turing machines can be equated to modern computers, it can solve any problem that is solvable by computers. Computability theory deals with verifying whether the problem is solvable or not and If it is solvable complexity theory deals with the algorithmic complexity of problems that are solvable by Turing Machine.This course mainly deals with automata theory (Mathematical Models) and its languages.

Overview

Section 1: Introduction to Automata Theory, Languages and Computation

Lecture 1 Introduction to this course

Lecture 2 Introduction to Automata - Languages - Chomsky Hierarchy

Lecture 3 Formal Languages: Strings, Languages

Lecture 4 Chomsky Hierarchy

Section 2: Introduction to Finite Automata

Lecture 5 Introduction to Finite Automata

Lecture 6 DFA and NFA

Lecture 7 DFA - Extended Transition Function and Language Acceptance

Lecture 8 NFA - Extended Transition Function and Language Acceptance

Lecture 9 Examples of DFA and NFA - language of strings

Lecture 10 Example DFA for complement of any language

Lecture 11 Finite Automaton with €- moves

Lecture 12 Finite Representation : Regular Expressions (RE)

Lecture 13 Pumping Lemma for RE

Section 3: Equivalence among Finite Automata

Lecture 14 Equivalence of NFA, DFA, NFA with €- moves and RE

Lecture 15 Working and examples for Subset construction Method

Lecture 16 NFA to DFA using Lazy subset construction Method

Lecture 17 Thomson's Construction Method for RE to Ꜫ-NFA

Lecture 18 Regular Expression to DFA

Lecture 19 Solved Examples for RE to DFA

Lecture 20 Minimization of DFA

Lecture 21 DFA to RE (Formula Method)

Lecture 22 Solved Examples for DFA to RE (Formula Method)

Lecture 23 Solved Examples for DFA to RE 3 states (Formula method)

Lecture 24 DFA to RE (State Elimination Method)

Section 4: Context Free Garmmar

Lecture 25 Introduction, Types of Grammar and Representation

Lecture 26 Context Free Grammar (CFG) and Languages

Lecture 27 Derivation, Parse tree and Ambiguity

Lecture 28 Simplification of CFG - Elimination of Useless Symbols

Lecture 29 Simplification of CFG - Elimination of Null productions

Lecture 30 Simplification of CFG - Elimination of Unit productions

Lecture 31 CFG to Chomsky Normal Form (CNF)

Lecture 32 Solved Examples - CFG to CNF

Lecture 33 CFG to Greibach Normal form

Lecture 34 Solved Examples - CFG to GNF

Lecture 35 Solved Examples - CNF to GNF

Section 5: Push Down Automata

Lecture 36 Introduction to Push Down Automata

Lecture 37 Problem in PDA {a^nb^n/n>1}

Lecture 38 Problem in PDA {a^n b^ m/n,m>=1} two problems (n>m) and (m>n)

Lecture 39 Problem in PDA { WCW^R/ w={a,b}*}

Lecture 40 Non-Deterministic PDA {Palindrome of a string}

Lecture 41 CFG (Context Free Grammar) to PDA (Push Down Automata)

Lecture 42 PDA (Push Down Automata) to CFG (Context Free Grammar)

Lecture 43 Pumping Lemma for CFG

Section 6: Turing Machine

Lecture 44 Introduction to Turing Machine, Instantaneous Description

Lecture 45 Turing Machine for Regular Language

Lecture 46 Turing Machine for Context Free Language

Lecture 47 TM for L={a^n b^n c^n / n>=0}

Lecture 48 TM for palindrome of a string over alphabet a,b

Lecture 49 TM for proper subtraction

Lecture 50 TM for Multiplication

Lecture 51 Modifications of TM

Lecture 52 Simulation of Turing Machine

Computer science students,Students preparing for Gate exams,Anyone planing for Government Exams in Computer Science base,Students interested in understanding the basic working of Models