Section outline

  • Collapse Expand

    INQ0091306 - AUTOMATA, LANGUAGES AND COMPUTATION 2025-2026 - PROF. GIORGIO SATTA

    Collapse all Expand all

    Content: Detailed description of course content and prerequisites can be found here.

    Textbook: The adopted textbook is Introduction to Automata Theory, Languages and Computation (3rd Edition) by John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman, Pearson New International Edition, 2018.

    Additional resources: As a complement to the textbook, the course also uses a collection of exercises with solutions, and two electronic forums for discussion of technical and administrative information. You can also access video recordings of the lectures from some past year at this link; to access this server you need to register.

    Logistics: Lectures are on Wednesday 10:30-12:00 (room Ae), Thursday 14:30-16:00 (room Ae), and Friday 10:30-12:00 (room Ae).

    Office hours: Thursday 12:30-14:15, email appointment required. Meetings can be in person or else on-line at this Zoom link.

    • Educational Offer Page URL
    • Announcements Forum

      Forum for general news and announcements. Only the lecturer can post in this forum. Subscription to this forum is automatic for every student who has registered to this course.

    • Class Forum

      Forum for discussion of technical matter presented during the lectures. Any student with a unipd account can post in this forum. Subscription to this forum is automatic for every student who has registered to this course.

    • Exercise collection File

      Collection of exercises with solutions, to be used to complement the textbook .

  • Collapse Expand

    Lecture 01

    October 1st, Wednesday (10:30-12:30)

    Course administration and presentation

    • Course timetable
    • Textbook & other material
    • Content outline & final exam
    • Statistics

    Introduction to the theory of automata

    • Examples of computational models
    • Recognition models and generative models
    • Proof techniques (to be revisited later)
    • Basics of formal language theory: alphabet and strings
    • Power of an alphabet and \(\Sigma^\ast\)

    References

    • Hopcroft et al., chapter 1
  • Collapse Expand

    Lecture 02

    October 2nd, Thursday (14:30-16:30)

    Introduction to the theory of automata

    • String concatenations and its properties
    • Notion of language
    • Extensional and intensional specification of a language
    • Set-formers
    • Languages and decision problems (to be revisited later)

    Finite state automata

    • Deterministic finite state automata (DFA)
    • String processing
    • Mathematical definition of DFA
    • Graphical representations for DFA
    • Extended transition function
    • Example

    References

    • Hopcroft et al., chapter 1
    • Hopcroft et al., chapter 2