IIT Guwahati Course , Prof. Diganta Goswami

**433**students enrolled

IIT Guwahati Course , Prof. Diganta Goswami

Introduction - Alphabet, Strings, Languages, Finite Representation of languages, Regular Expressions - 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 - 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 - Myhill-Nerode Theorem and minimization of finite automata - Establishing the equivalence between regular languages, regular grammars and finite automata 2DFA, Moore and Mealy automata - Some closure properties of Regular languages -Closure under Boolean operations, reversal, homomorphism, inverse homomorphism, etc. Pumping lemma, proving languages to be non regular. - Simplification of CFGs

Removing useless symbols, epsilon- Productions, and unit productions, Normal forms -CNF and GNF - Some closure properties of CFLs -Closure under union, concatenation, Kleene closure, substitution,homomorphism, reversal, intersection with regular set, etc. Pumping lemma - Pushdown automata and showing the equivalence between PDA and CFG - 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 - Grammars and grammatically computable functions - 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 language, The Halting problem, Undecidable problems about TMs - Time bounded TMs, The classes P, NP and NP-complete, Cook's Theorem, Some NP-complete problems - Context-sensitive languages, linear bounded automata and Chomsky Hierarchy.

Removing useless symbols, epsilon- Productions, and unit productions, Normal forms -CNF and GNF - Some closure properties of CFLs -Closure under union, concatenation, Kleene closure, substitution,homomorphism, reversal, intersection with regular set, etc. Pumping lemma - Pushdown automata and showing the equivalence between PDA and CFG - 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 - Grammars and grammatically computable functions - 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 language, The Halting problem, Undecidable problems about TMs - Time bounded TMs, The classes P, NP and NP-complete, Cook's Theorem, Some NP-complete problems - Context-sensitive languages, linear bounded automata and Chomsky Hierarchy.

Up Next

You can skip ad in

SKIP AD >

Advertisement

- 2x
- 1.5x
- 1x
- 0.5x
- 0.25x

EMBED LINK

COPY

DIRECT LINK

COPY

PRIVATE CONTENT

OK

Enter password to view

Please enter valid password!

- Play Pause
- Mute UnMute
- Fullscreen Normal
- @Your Company Title

0:00

0 (0 Ratings)

Formal Languages and Automata Theory by Dr. Diganta Goswami & Dr. K.V. Krishna,Department of Mathematics,IIT Guwahati.For more details on NPTEL visit httpnptel.ac.in.

0%

0%

0%

0%

0%

- 1.Introduction
- 2.Alphabet, Strings, Languages
- 3.Finite Representation
- 4.Grammars (CFG)
- 5.Derivation Trees
- 6.Regular Grammars
- 7.Finite Automata
- 8.Nondeterministic Finite Automata
- 9.NFA DFA
- 10.Myhill-Nerode Theorem
- 11.Minimization
- 12.RE FA
- 13.FA RE
- 14.FA RG
- 15.Variants of FA
- 16.Closure Properties of RL
- 17.Homomorphism
- 18.Pumping Lemma
- 19.Simplification of CFG
- 20.Normal Forms of CFG
- 21.Properties of CFLs
- 22.Pushdown Automata
- 23.PDA CFG
- 24.Turing Machines Definitions and Examples
- 25.Turing Computable Functions
- 26.Combining Turing Machines
- 27.Multi Input
- 28.Turing Decidable Languages
- 29.Varients of Turing Machines
- 30.Structured Grammars
- 31.Decidability
- 32.Undecidability1
- 33.Undecidability2
- 34.Undecidability3
- 35.Time Bounded Turing Machines
- 36.P and NP
- 37.NP-Completeness
- 38.NP-Complete Problems1
- 39.NP-Complete Problems2
- 40.NP-Complete Problems3
- 41.Chomsky Hierarchy
- 42.Chomsky Hierarchy I

- FreeVideoLectures aim to help millions of students across the world acquire knowledge, gain good grades, get jobs, assist in getting promotions through quality learning material.

- You can write to us
- help@freevideolectures.com

2018 FreeVideoLectures. All rights reserved. FreeVideoLectures only promotes free course material from different sources, we are not endrosed by any university.