Formal Language And Automata: Finite Automata And Re

Theory of Computation

What you'll learn

Deterministic Finite Automata

Non-deterministic Finite Automata

Conversion of NFA to DFA and Epsilon NFA to DFA

Regular Expressions

Requirements

Basic Mathematical Knowledge

Description

Formal Language and Automata: Finite Automata and RE is a fundamental course in theoretical computer science that delves into the mathematical principles governing computational systems and algorithms. This course is designed for third-year Engineering students, the course provides a structured understanding of formal languages, automata theory, and their significance in defining and influencing computation.The course begins with an introduction to formal languages, and their classifications, focusing on regular languages. Students will explore different ways to represent these languages, such as deterministic finite automata (DFA), non deterministic finite automata (NFA), and regular expressions (RE). Through rigorous analysis, they will understand the computational power of these models and the fundamental equivalence between them. Key topics include minimisation of finite automata, pumping lemma and decision problems associated with regular languages.Beyond theoretical concepts, this course emphasizes practical applications in areas like compiler design, lexical analysis, pattern matching, text processing, and software verification. Students will engage in mathematical proofs, algorithmic problem-solving, and interactive exercises to reinforce their learning.By the end of the course, students will have a solid grasp of computational models, enabling them to design efficient algorithms, comprehend system constraints, and explore advanced topics in artificial intelligence, cryptography, and software engineering.

Overview

Section 1: Deterministic Finite Automata

Lecture 1 Basic Definitions in Automata

Lecture 2 DFA with Example

Lecture 3 DFA Example: Start with "01"

Lecture 4 DFA Example: Substring "101"

Lecture 5 DFA Example: Does not contain substring "101"

Lecture 6 DFA Example: Binary String is even

Lecture 7 DFA Example: Divisible by 3

Lecture 8 DFA Example: Even 0's and Even 1's

Lecture 9 Extended Transition Function for DFA

Section 2: Non-Deterministic Finite Automata and Conversions

Lecture 10 NFA with Example

Lecture 11 NFA Example

Lecture 12 Extended Transition Function for NFA

Lecture 13 NFA to DFA Conversion

Lecture 14 NFA to DFA : Another Example

Lecture 15 ε-NFA

Lecture 16 ε-Closure

Lecture 17 Conversion of ε-NFA to DFA

Lecture 18 Minimized DFA

Section 3: Regular Expressions

Lecture 19 Introduction to Regular Expression

Lecture 20 RE to Epsilon-NFA Conversion

Lecture 21 DFA to RE Conversion

Lecture 22 DFA to RE Example1

Lecture 23 DFA to RE Example2

Lecture 24 Pumping Lemma for Regular Languages

Lecture 25 Pumping Lemma: Example 1

Lecture 26 Pumping Lemma: Example 2

Computer Science and Engineering Students