You can download the lectures here. We will try to upload lectures prior to their corresponding classes.

  • Finite Automata
    tl;dr: The document covers the fundamentals of Finite Automata (FA), including alphabets, strings, and languages, with examples of Deterministic Finite Automata (DFA) and Non-deterministic Finite Automata (NFA). It also discusses DFA/NFA construction, minimization, and handling ε-transitions, with practical examples and diagrams illustrating the conversion between NFA and DFA
    [slides]
  • Regular Expression - Part 1
    tl;dr: Introduces regular expressions as an algebraic way to describe regular languages, covering their formal definition (basis cases like symbols and ε, inductive cases like union, concatenation, and Kleene closure) and establishing their equivalence to finite automata.
    [slides]
  • Regular Expression - Part 2
    tl;dr: Explains three methods for converting regular expressions to automata, Thomson's construction (RE to NFA), subset construction (NFA to DFA), and direct construction (RE to DFA using syntax trees with followpos, firstpos, and lastpos functions).
    [slides]
  • Closure Properties of Regular Languages
    tl;dr: Union, Intersection, Difference Concatenation, Kleene Closure, Reversal, Homomorphism, Inverse Homomorphism
    [slides]
  • Regular Expression - Additional Resources
    tl;dr: Explains regular expressions as an algebraic framework equivalent to DFAs for describing regular languages, covering syntax, identities, and practical pattern examples. It also shows how to systematically convert regular expressions to NFAs, including constructions for union, concatenation, star, and generalized transitions.
    [slides]
  • Context Free Grammar
    tl;dr: A concise introduction to context free grammars covering derivations, parse trees, ambiguity resolution, left recursion elimination, left factoring, and the limits of CFGs in programming language constructs
    [slides]
  • Pushdown Automata
    tl;dr: This document introduces Pushdown Automata as finite automata extended with stack memory, explaining how they characterize context-free languages and differ from regular languages. It formally defines PDA, DPDA, and NPDA, compares their expressive power, and demonstrates PDA constructions for languages with both empty stack and final state acceptance.
    [slides]
  • Pushdown Automata (Part -2)
    tl;dr: This document introduces Pushdown Automata as finite automata extended with stack memory, explaining how they characterize context-free languages and differ from regular languages. It formally defines PDA, DPDA, and NPDA, compares their expressive power, and demonstrates PDA constructions for languages with both empty stack and final state acceptance.
    [slides]