Automata theory and grammars (A&G) - KAIN5M06

  • Number of hours

    • Lectures 16.0
    • Projects -
    • Tutorials 14.0
    • Internship -
    • Laboratory works 4.0
    • Written tests 4.5

    ECTS

    ECTS 0.5

Goal(s)

The course "Automata & Grammars" has 4 components:

  • The presentation of fundamental results of computer science: a technique of correctness proof of programs, different computation models (sequential, parallel, non-deterministic), the computation in finite time of operations on infinite data (the languages represented as automata), recursion
  • The illustration of these notions in the case of automata and grammars
  • A concrete example of recent use of automata: verification of drivers, medical protocols, autonomous character in video games, ...
  • A concrete example of the use of attributed grammars

Targeted skills

  • know how to prove that a program is correct
  • know how to program using an automaton
  • know how to write a simple analyzer / translator

Content(s)

  • Proof of partial program correctness by the Floyd-Hoare-Dijkstra technique: how to be sure that a program is doing what is expected. In other words, will you get on the plane which runs an autopilot you programmed?
  • Automata (with finite state / stack numbers, deterministic / non-deterministic): what is the computation model of a processor? are there languages ?more powerful than others?
  • Equivalent representations (from Regular Grammars to Arden's Equations then to Regular Expressions and finally to Finite State Automata): how do we go from a readable description to a version usable by a processor?
  • Application and implementation of Automata (ie. Programmable Logic Controller): PLC are used to program (lexical analyzers, micro-controllers, interfaces, protocols, games, ...), to control (production chains, physical, ...) and to check (drivers, security policies ...) in fact we find them everywhere.
  • Attributed and Generative Grammars: Grammars are the everyday tool of developpers who translate language or data from one format to another.
  • Application (mini-project): implementation of a data format translator using a syntactic parser generator (ANTLR or JavaCC)

Prerequisites

Basic knowledge of an imperative language such as C

Test

  • 75% CC
  • 25% EXAM
    • in person
    • written test online on PC with the SafeExamBrowser software under Windows or macOs
    • 1h30
    • adaptation to disability: extended test time
    • no document allowed
    • authorized electronic devices: PC only

Calendar

The course exists in the following branches:

  • Curriculum - INFO - Semester 5

Additional Information

Course ID : KAIN5M06
Course language(s): FR

You can find this course among all other courses.

Bibliography

Pour aller plus loin :

  • en français

1. Introduction à la calculabilité - Pierre Wolper - Éditions Dunod (3eme édition, 2006)
2. Compilateurs: principes, techniques et outils - A.V. Aho, M.S. Lam, R. Sethi, J.D. Ullman - Éditions Pearson France éduction (2nde édition, 2007)

  • en anglais

1. Introduction to Automata Theory, Languages, and Computations - J.E.Hopcroft, R.Motwani, J.D.Ullman - Pearson Editor (3rd edition)
2. Compilers: Principles, Techniques, and Tools - A.V.Aho, M.S.Lam, R.Sethi, J.D.Ullman - Pearson Editor (2nd edition, 2007)