Theory Of Automata | Formal Language And Automata Theory

An Introduction to the Theory of Automata

What you'll learn

Define Finite Automata

Construct deterministic and non-deterministic machines.

Understand Language and its relation to Finite automata

Construct Push down Automata and Turing Machine.

Understand Decidable and Undecidable problem.

Requirements

No programming required

Description

Formal language and automata theory is a branch of theoretical computer science that explores the mathematical properties of formal languages and their relationship to automata. It is concerned with the study of abstract machines and the languages they can recognize or generate.Formal language and automata theory is a fundamental area of computer science that delves into the study of formal languages, which are sets of strings of symbols, and automata, which are abstract machines that process these strings. The theory aims to understand the relationship between these two concepts and the computational processes they represent.In this field, formal languages are described using mathematical structures, such as regular expressions and context-free grammars, and these languages are then associated with different types of automata, including finite automata, pushdown automata, and Turing machines. By studying these relationships, researchers aim to uncover the fundamental capabilities and limitations of computational systems.This theory has broad applications in various areas of computer science, including compiler design, natural language processing, and the analysis of algorithms. It also plays a crucial role in the development of programming languages and the design of software systems.Overall, formal language and automata theory provides a theoretical foundation for understanding the nature of computation and is essential for the advancement of computer science as a discipline.

Overview

Section 1: Introduction

Lecture 1 Introduction to Theory of Computation

Lecture 2 Pre-requisite for Theory of Computation

Section 2: Deterministic Finite Automata and Non Deterministic Finite Automata

Lecture 3 Basic Understanding of Finite Automata

Lecture 4 Deterministic Finite Automata

Lecture 5 Deterministic Finite Automata Example

Lecture 6 Operations on DFA-1

Lecture 7 Operations on DFA -2

Lecture 8 Non Deterministic Finite Automata

Lecture 9 Examples on Non Deterministic Automata

Lecture 10 More Examples on Non Deterministic Automata

Lecture 11 Difference between DFA and NFA

Lecture 12 Epsilon- NFA

Lecture 13 Conversion of epsilon NFA to NFA

Lecture 14 Conversion of NFA to DFA

Lecture 15 Equivalence of Finite Automata

Lecture 16 Minimization of States ( Partition Method )

Lecture 17 Minimization of states ( Myhill - Nerode theorem)

Section 3: Regular Expression and Finite Auromata

Lecture 18 Regular set and Regular Expression

Lecture 19 Conversion of DFA to Regular Expression ( State Elimination Method)

Lecture 20 Application of Adern's Theorem

Lecture 21 Conversion of Regular Expression to Finite Automata

Lecture 22 Pumping Lemma

Section 4: Grammar

Lecture 23 Introduction to Grammar

Lecture 24 Context free Grammar

Lecture 25 Construction of Finite Automata to Grammar

Lecture 26 Conversion of Left Linear Grammar to Right Linear Grammar

Lecture 27 Conversion of Right Linear Grammar to Left Linear Grammar

Lecture 28 Ambiguity in Grammar

Lecture 29 Removal of Useless Symbol

Lecture 30 Removal of Null- Production

Lecture 31 Removal of Unit Product

Lecture 32 Chomsky Normal Form

Lecture 33 Greibach Normal Form

Lecture 34 Decision Problem for Context free Grammar-1

Lecture 35 Decision Problem for Context free Grammar-2

Lecture 36 Pumping Lemma for Context free grammar

Lecture 37 Closure property of Context free language-1

Lecture 38 Closure property of Context free language-2

Lecture 39 Introduction to Pushdown Automata

Lecture 40 Examples on Pushdown Automata-1

Lecture 41 Examples on Pushdown automata-2

Lecture 42 Examples on Pushdown Automata-3

Lecture 43 Examples on Pushdown Automata-4

Lecture 44 Examples on Pushdown Automata-5

Lecture 45 Equivalence of Context free grammar and Pushdown Automata

Lecture 46 Equivalence of Contextfree grammat and Pushdown-2

Lecture 47 Introduction to Turing Machine

Lecture 48 Examples on Turing machine -1

Lecture 49 Examples on Turing machine-2

Lecture 50 Examples on Turing Machine-3

Lecture 51 Examples on Turing machine-4

Lecture 52 Examples on Turing Machine-5

Lecture 53 Examples on Turing Machine-6

Lecture 54 Examples on Turing Machine-7

Lecture 55 Touring machine-Subroutine

Lecture 56 Variants of Turing Machine

Lecture 57 Universal Turing machine

Lecture 58 Decidability and Undecidability

Lecture 59 Halting Problem

Beginner to Intermediate level B Tech, M Tech, MCA and any other Engineering Students