Add to Wishlist

Formal Languages and Automata Theory

Duration: 32:11:00
Lectures: 41
Level: Beginner

Archive

unit 1: (D. Goswami)
Introduction to the course. Texts and References are given.

Unit 2: (D. Goswami)
Alphabet,Strings, Languages, Finite Representation of languages, Regular
Expressions.

Unit 3: (K. V. Krishna)
Context-free Grammars (CFGs) -Formal definition, sentential forms, leftmost and
rightmost derivations,, the language of a CFG. Derivation tree or Parse tree –
Definition, Relationship between parse trees and derivations.Parsing and ambiguity,
Ambiguity in grammars and Languages. Regular grammars.

Unit 4: (D. Goswami)
Finite automata (FA) -its behavior; DFA -Formal definition, simplified notations (state
transition diagram, transition table), Language of a DFA. NFA -Formal definition,
Language of an NFA, Removing, epsilon-transitions.Equivalence of DFAs and
NFAs.

Unit 5: (K. V. Krishna)
Myhill-Nerode Theorem and minimization of finite automata

Unit 6: (D. Goswami)
Establishing the equivalence between regular languages,regular grammars and
finite automata.

Unit 7: (K. V. Krishna)
2DFA, Moore and Mealy automata.

Unit 8: (K. V. Krishna)
Some closure properties of Regular languages -Closure under Boolean operations,
reversal, homomorphism, inverse homomorphism, etc.Pumping lemma, proving
languages to be non regular.

Unit 9: (D. Goswami)
Simplification of CFGs -Removing useless symbols, epsilon- Productions, and unit
productions, Normal forms -CNF and GNF

Unit 10: (K. V. Krishna)
Some closure properties of CFLs -Closure under union, concatenation,Kleene
closure, substitution, homomorphism,reversal, intersection with regular set, etc.
Pumping lemma.

Unit 11: (K. V. Krishna)
Pushdown automata and showing the equivalence between PDA and CFG.

Unit 12: (K. V. Krishna)
Turing Machines TM -Formal definition and behavior, Transition diagrams, Language
of a TM, TM as accepters and deciders. TM as a computer of integer functions.
Variants of Turing machines.

Unit 13: (K. V. Krishna)
Grammars and grammatically computable functions.

Unit 14: (D. Goswami)
Recursive languages,Some properties of recursive and recursively enumerable
languages, Codes for TMs.A language that is not recursively enumerable (the
diagonalization language). The universal language, Undecidability of the universal
.
Unit 15: (K. V. Krishna)
Time bounded TMs, The classes P, NP and NP-complete, Cook’s Theorem,Some
NP-complete problems.

Unit 16: (D. Goswami)
Context-sensitive languages, linear bounded automata and Chomsky Hierarchy.

1
Formal Languages and Automata Theory -Lec :01- Introduction
34:23
2
Formal Languages and Automata Theory -Lec :02 -Alphabet, Strings, Languages
45:18
3
Formal Languages and Automata Theory -Lec :03 -Finite Representation
52:42
4
Formal Languages and Automata Theory -Lec :04 -Grammars (CFG)
49:06
5
Formal Languages and Automata Theory -Lec :05 -Derivation Trees
50:06
6
Formal Languages and Automata Theory -Lec :06 -Regular Grammars
54:07
7
Formal Languages and Automata Theory -Lec :07 -Finite Automata
51:09
8
Formal Languages and Automata Theory -Lec :08 -Nondeterministic Finite Automata
50:13
9
Formal Languages and Automata Theory -Lec :09 -NFA <=> DFA
1:03:11
10
Formal Languages and Automata Theory -Lec :10 -Myhill-Nerode Theorem
52:02
11
Formal Languages and Automata Theory -Lec :11 -Minimization
50:44
12
Formal Languages and Automata Theory -Lec :12 -RE => FA
58:41
13
Formal Languages and Automata Theory -Lec :13 -FA => RE
59:30
14
Formal Languages and Automata Theory -Lec :14 -FA <=> RG
48:55
15
Formal Languages and Automata Theory -Lec :15 -Variants of FA
56:02
16
Formal Languages and Automata Theory -Lec :16 -Closure Properties of RL
48:39
17
Formal Languages and Automata Theory -Lec :17 -Homomorphism
54:13
18
Formal Languages and Automata Theory -Lec :18 -Pumping Lemma
50:54
19
Formal Languages and Automata Theory -Lec :19 -Simplification of CFG
1;00:49
20
Formal Languages and Automata Theory -Lec :20 -Normal Forms of CFG
57:21
21
Formal Languages and Automata Theory -Lec :21 -Properties of CFLs
47:57
22
Formal Languages and Automata Theory -Lec :22 -Pushdown Automata
54;31
23
Formal Languages and Automata Theory -Lec :23 -PDA <=> CFG
48:52
24
Formal Languages and Automata Theory -Lec :24 -Turing Machines
57:35
25
Formal Languages and Automata Theory -Lec :25 -Turing Computable Functions
54:26
26
Formal Languages and Automata Theory -Lec :26- Combining Turing Machines
53:43
27
Formal Languages and Automata Theory -Lec :27 -Multi Input
51:59
28
Formal Languages and Automata Theory -Lec :28 -Turing Decidable Languages
48:06
29
Formal Languages and Automata Theory -Lec :29 -Varients of Turing Machines
52:45
30
Formal Languages and Automata Theory -Lec :30 -Structured Grammars
52:16
31
Formal Languages and Automata Theory -Lec :31 -Decidability
36:01
32
Formal Languages and Automata Theory -Lec :32 -Undecidability1
49:32
33
Formal Languages and Automata Theory -Lec :33 -Undecidability2
53:52
34
Formal Languages and Automata Theory -Lec :34 -Undecidability3
52:15
35
Formal Languages and Automata Theory -Lec :35 -Time Bounded Turing Machines
46:41
36
Formal Languages and Automata Theory -Lec :36 -P and NP
50:50
37
Formal Languages and Automata Theory -Lec :38 -NP-Complete Problems1
49
38
Formal Languages and Automata Theory -Lec :37 -NP-Completeness
47:28
39
Formal Languages and Automata Theory -Lec :39 -NP-Complete Problems2
41:31
40
Formal Languages and Automata Theory -Lec :40 -NP-Complete Problems3
50:37
41
Formal Languages and Automata Theory -Lec :41 -Chomsky Hierarchy
46:44

Be the first to add a review.

Please, login to leave a review
Formal Languages and Automata Theory
Price:
Free