Theory of Automata | Formal Language and Automata Theory

Name: Theory of Automata | Formal Language and Automata Theory
Rating: 4.7 (15 reviews)

An Introduction to the Theory of Automata

Created byRakesh Nayak

Last updated 2/2024

English

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.

Course content

4 sections • 59 lectures • 10h 32m total length

Introduction to Theory of Computation11:59
This video describes about the Introduction to Theory of Computation otherwise known as Formal Language and Automata Theory
Pre-requisite for Theory of Computation16:13
This video describes about the pre-requisite to Theory of Computation, which contents the terminology for the subject.

Basic Understanding of Finite Automata17:06
This video will help to understand the the representation method for any finite automata
Deterministic Finite Automata16:02
Deterministic Finite Automata Example14:19
This video describes Deterministic Finite Automata with simple example
Operations on DFA-114:49
This video describes about different operations in Deterministic Finite Automata.
Operations on DFA -28:57
This video describes about Some more operations on Deterministic Finite Automata.
Non Deterministic Finite Automata12:18
This video describes about Non Deterministic Finite Automata with simple example
Examples on Non Deterministic Automata10:53
This video describes about Simple examples on Non Deterministic Finite Automata.
More Examples on Non Deterministic Automata11:29
This video describes about some more examples on Non Deterministic Finite Automata
Difference between DFA and NFA2:27
This video describe about the difference between DFA and NFA
Epsilon- NFA9:34
This video describe about epsilon- NFA
Conversion of epsilon NFA to NFA9:50
This video describes about Conversion of epsilon NFA to NFA
Conversion of NFA to DFA12:24
This video describe about Conversion of NFA to NFA
Equivalence of Finite Automata11:07
This video describes the equivalence of Finite Automata
Minimization of States ( Partition Method )13:37
This video describes the method to minimize states in a finite automata
Minimization of states ( Myhill - Nerode theorem)13:49
This video describes about Minimization of states by using Myhill - Nerode theorem.

Introduction to Grammar10:00
Understand formal grammar as rules to generate syntactically correct strings, explore the Chomsky hierarchy from type 3 to type 0, and define terminals, nonterminals, start symbol, and productions.
Context free Grammar14:02
Construction of Finite Automata to Grammar8:31
Conversion of Left Linear Grammar to Right Linear Grammar9:40
Explore left linear and right linear grammars and how to convert a left linear grammar into a right linear one via finite automata, state interchange, and reversed transitions.
Conversion of Right Linear Grammar to Left Linear Grammar7:41
Ambiguity in Grammar10:29
Removal of Useless Symbol11:33
Removal of Null- Production10:12
Identify nullable variables in a context-free grammar and systematically remove epsilon productions by generating new productions that include or exclude nullable symbols, preserving the language.
Removal of Unit Product4:35
Chomsky Normal Form12:58
Greibach Normal Form11:29
Explore Greibach normal form, its relation to Chomsky normal form, and context-free grammar conversion steps. Eliminate null and unit productions, remove left recursion, and enable direct pushdown automaton recognition.
Decision Problem for Context free Grammar-16:36
Decision Problem for Context free Grammar-215:27
Pumping Lemma for Context free grammar9:08
Closure property of Context free language-114:54
Closure property of Context free language-28:54
Introduction to Pushdown Automata11:43
Examples on Pushdown Automata-18:33
Examples on Pushdown automata-213:30
Examples on Pushdown Automata-314:39
This lecture shows a pushdown automaton for the language a^(m+n) b^n c^m with m,n≥1, using a stack to push a’s and pop on b’s and c’s, accepting by empty stack.
Examples on Pushdown Automata-410:22
Examples on Pushdown Automata-511:08
Construct a pushdown automaton that accepts the language w, c, w by pushing w's symbols, reading c, and then popping to verify the reverse.
Equivalence of Context free grammar and Pushdown Automata12:26
Equivalence of Contextfree grammat and Pushdown-213:29
Construct a context-free grammar from a given pushdown automaton by deriving variables from states and stack symbols and translating transitions into productions with a matching start symbol.
Introduction to Turing Machine9:10
Examples on Turing machine -112:19
Explore how a deterministic Turing machine, defined by seven tuples, reads binary input and accepts or rejects strings that begin or end with one.
Examples on Turing machine-212:13
Examples on Turing Machine-35:54
The lecture designs a Turing machine over zero and one that accepts substring zero one, with any zeros and ones before and after, using x and y marks.
Examples on Turing machine-48:55
Examples on Turing Machine-510:03
Examples on Turing Machine-615:19
Examples on Turing Machine-712:04
Touring machine-Subroutine9:33
Variants of Turing Machine7:42
Universal Turing machine5:42
Explore the universal Turing machine by encoding a TM and its input in binary. A universal language is a Turing recognizable binary set that may accept, reject, or loop.
Decidability and Undecidability3:53
Halting Problem4:37
Explore the halting problem in Turing machines, showing that no algorithm can decide all programs' halting behavior. Understand why this undecidability follows from the Turing thesis and computability limits.

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.

Who this course is for:

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

Theory of Automata | Formal Language and Automata Theory

What you'll learn

Explore related topics

Course content

Introduction2 lectures • 28min

Deterministic Finite Automata and Non Deterministic Finite Automata15 lectures • 2hr 59min

Regular Expression and Finite Auromata5 lectures • 55min

Grammar37 lectures • 6hr 19min

Requirements

Description

Who this course is for: