Deterministic Finite Automata (Theory of Computation)

Name: Deterministic Finite Automata (Theory of Computation)
Rating: 4.8 (145 reviews)

DFA example solving with easy tricks.

Highest Rated

Created byNeha Pradyumna Bora

Last updated 6/2023

English

What you'll learn

Students will learn the basics of theory of computation
Students will learn about Real time problems of TOC
Students will learn and able to solve the Deterministic Finite Automata
One will be able to answer all questions of DFA in important exams like GATE

Course content

1 section • 12 lectures • 4h 12m total length

Introduction9:19
Introduction to Theory of Computation
Some Important Terms13:58
Some Important Terms before staring with course
FA types and DFA Definition5:21
FA Types DFA Definition
DFA Example: String that ends with 110:17
DFA Example: DFA accepting a string that ends with 1 on ∑ (0,1)
DFA Example: String if no. of 1’s is odd11:47
DFA Example: DFA accepting a string if no. of 1’s is odd on ∑ (0,1)
DFA Example: String is having Number of 1 in multiple of 327:53
DFA Example:
1. Number of 1’s is a multiple of 3.
2. Number of 1’s is not multiple of 3
DFA Example: String length and counting related26:30
DFA Example:
Draw DFA for the following language over { 0,1}
1. All strings of length at most 5 (max to max)
2. All strings with exactly two ones
3. All strings containing at least two zeros (minimum)
4. All strings containing at most two zeros
5. All strings starting with 1 and the length of the string is divisible by 3
DFA Example: String position and substring related problem27:53
DFA Example:
Draw DFA for the following language over{ a,b}
1. All strings starting with abb
2. All strings with abb as a substring i.e abb is anywhere in the string
3. All strings ending in abb
DFA Example: Divisibility Problem10:41
DFA Example:
Design a DFA which can accept a decimal no. divisible by 3.
DFA Example: Divisibility Problem5:58
DFA Example:
Design a DFA which can accept a binary no. divisible by 3.
Real time example of Vending Machine6:51
DFA Examples:
Real time example of Vending Machine
Revision1:36:30

Requirements

Discrete Mathematics still No there is no as such requirement for learning the course proceedings.

Description

This is an introductory course on the theory of computation intended for undergraduate students in computer science. It is one of the highly mathematical and logical subjects, which will help students think and increase their reasoning capabilities. In this course, we will introduce various models of computation. The theory of Computation plays an important role in computer science. I'm aware that many students don't see the importance of a mathematical approach to CS. They are essential for describing the syntax of programming languages and are a part of every compiler. They also play an important role in describing the syntax of natural languages and are used in software that does machine translation and other natural language processing.

Finite Automata

Today we begin with an informal introduction to finite automata. The finite automaton is a mathematical model,

We will also explore Finite Automata, Types of FA, Languages, Deterministic Finite Automata, and examples of DFA. Complicated examples are explained in very easy language and with some solving tricks.

It is a core subject so all the Product / Service based Industry needs it. It is broadly used in the design of Programming Languages and their Compilers. Real-time application of TOC in ATM m/c, Lifts, Spell checkers, Lex and YACC Compilers, Vending m/c, etc.

Who this course is for:

Anyone who is interested in learning theory of computation and its concepts.