Introduction to Automata Theory, Languages and Computation
- Description
- Curriculum
- FAQ
- Reviews
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 namely
1) Automata Theory
2) Computability Theory
3) Complexity Theory
The 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.
-
6Introduction to Finite AutomataVideo lesson
-
7DFA and NFAVideo lesson
-
8DFA - Extended Transition Function and Language AcceptanceVideo lesson
-
9NFA - Extended Transition Function and Language AcceptanceVideo lesson
-
10Examples of DFA and NFA - language of stringsVideo lesson
-
11Example DFA for complement of any languageVideo lesson
-
12Finite Automaton with €- movesVideo lesson
-
13Finite Representation : Regular Expressions (RE)Video lesson
-
14Pumping Lemma for REVideo lesson
-
15Finite AutomataQuiz
-
16Equivalence of NFA, DFA, NFA with €- moves and REVideo lesson
-
17Working and examples for Subset construction MethodVideo lesson
-
18NFA to DFA using Lazy subset construction MethodVideo lesson
-
19Thomson's Construction Method for RE to Ꜫ-NFAVideo lesson
-
20Regular Expression to DFAVideo lesson
-
21Solved Examples for RE to DFAVideo lesson
-
22Minimization of DFAVideo lesson
-
23Epsilon NFA to NFAVideo lesson
-
24DFA to RE (Formula Method)Video lesson
-
25Solved Examples for DFA to RE (Formula Method)Video lesson
-
26Solved Examples for DFA to RE 3 states (Formula method)Video lesson
-
27DFA to RE (State Elimination Method)Video lesson
-
28Finite Automata - Example 1 - Scenario QuestionVideo lesson
-
29Finite Automata - Example 2 - Scenario based questionVideo lesson
-
30Finite Automata - Example 3 - Scenario based question for DFA constructionVideo lesson
-
31Equivalence of Finite AutomataQuiz
-
37Introduction, Types of Grammar and RepresentationVideo lesson
-
38Context Free Grammar (CFG) and LanguagesVideo lesson
-
39Example 1: CFG constructionVideo lesson
-
40Example 2: CFG constructionVideo lesson
-
41Example 3: CFG constructionVideo lesson
-
42Derivation, Parse tree and AmbiguityVideo lesson
-
43Simplification of CFG - Elimination of Useless SymbolsVideo lesson
-
44Simplification of CFG - Elimination of Null productionsVideo lesson
-
45Simplification of CFG - Elimination of Unit productionsVideo lesson
-
46CFG to Chomsky Normal Form (CNF)Video lesson
-
47Scenario based example for CNFVideo lesson
-
48Solved Examples - CFG to CNFVideo lesson
-
49CFG to Greibach Normal formVideo lesson
-
50Solved Examples - CFG to GNFVideo lesson
-
51Solved Examples - CNF to GNFVideo lesson
-
52Scenario GNFVideo lesson
-
53Example 1 - Scenario based question for CNF and GNFVideo lesson
-
54Context Free GrammarQuiz
-
55Introduction to Push Down AutomataVideo lesson
-
56Problem in PDA {a^nb^n/n>1}Video lesson
-
57Problem in PDA {a^n b^ m/n,m>=1} two problems (n>m) and (m>n)Video lesson
-
58Problem in PDA { WCW^R/ w={a,b}*}Video lesson
-
59Non-Deterministic PDA {Palindrome of a string}Video lesson
-
60CFG (Context Free Grammar) to PDA (Push Down Automata)Video lesson
-
61PDA (Push Down Automata) to CFG (Context Free Grammar)Video lesson
-
62Pumping Lemma for CFGVideo lesson
-
63Scenario based question in CFG and PDAVideo lesson
-
64Push Down AutomataQuiz
-
65Introduction to Turing Machine, Instantaneous DescriptionVideo lesson
-
66Turing Machine RepresentationsVideo lesson
-
67Turing Machine for Regular LanguageVideo lesson
-
68Turing Machine for Context Free LanguageVideo lesson
-
69TM for L={a^n b^n c^n / n>=0}Video lesson
-
70TM for palindrome of a string over alphabet a,bVideo lesson
-
71TM for proper subtractionVideo lesson
-
72TM for MultiplicationVideo lesson
-
73Modifications of TMVideo lesson
-
74Simulation of Turing MachineVideo lesson
-
75Turing MachineQuiz
-
76Example 1 : Regular Language - construction of DFA, PDA and TMVideo lesson
-
77Example 2 : Context Free Language - Construction of PDA and TMVideo lesson
-
78Example 3 : Turing Machine problemVideo lesson
-
79Example 4 : Turing Machine for 1's ComplementVideo lesson
-
80Example 5 : scenario based question in Turing MachineVideo lesson
-
81Example 6 : scenario based question in Turing MachineVideo lesson
-
82Example 7 : scenario based question in Turing MachineVideo lesson
-
83Example 8 : scenario based question in PDA and CFGVideo lesson
External Links May Contain Affiliate Links read more