Conceptual Tools
Guy Perrier
Degree in Computer Science and Cognitive Science
Specialization :  Computation Methods Applied to Management
Université de Lorraine
The aim of the course is to allow students to appropriate conceptuals tools in the areas of formal languages, computation models and predicate logic, which are used in the design and compilation of programming languages as in query languages for databases.

The course is divided into two parts :
  1. Formal languages and computation models
    1. Introduction to formal languages and computation models (slides)
      We introduce general concepts related to formal languages and computation around the notion of Turing machine.

    2. Finite State Automata and Regular Languages (slides)
      We present the notions of regular expressions, deterministic and non-deterministic finite state automata,automata determinization and minimization. Finally, we show the relationship between regular languages and finite state automata.

    3. Context Free Grammars and Push Down Automata (slides)
      We define Context Free Grammars with different ways of normalisation, especially the elimination of left recursivity. Then, we present Push Down Automata as the computation model associated with Context Free Grammars.

  2. Predicate Logic (slides)
    1. First order languages
      First, we present the syntax of first order logic formulas with the distinction between terms and formulas, the distinction between free variables and bound variables and the operation of substitution.

    2. Models and validity of logical formulas
      We define the notion of interpretation of a formula with respect to a model. From this, we establish the distinction between satisfiable and inconsistent formulas and define the notion of tautology.

    3. The Predicate Calculus
      We present the predicate calculus in the form of a natural deduction system for the predicate logic.

Bibliography