Formal Languages and Automata Theory

IIT Guwahati Course , Prof. Diganta Goswami

245 students enrolled

Overview

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.

Lecture 12: RE FA

Up Next
You can skip ad in
SKIP AD >
Advertisement
      • 2x
      • 1.5x
      • 1x
      • 0.5x
      • 0.25x
        EMBED LINK
        COPY
        DIRECT LINK
        PRIVATE CONTENT
        OK
        Enter password to view
        Please enter valid password!
        0:00
        0 (0 Ratings)

        Lecture Details

        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.

        LECTURES



        Review


        0

        0 Rates
        1
        0%
        0
        2
        0%
        0
        3
        0%
        0
        4
        0%
        0
        5
        0%
        0

        Comments Added Successfully!
        Please Enter Comments
        Please Enter CAPTCHA
        Invalid CAPTCHA
        Please Login and Submit Your Comment