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
:
- Formal languages and computation
models
- Introduction to formal
languages and computation models (slides)
We introduce general concepts related to formal languages and
computation around the notion of Turing machine.
- 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.
- 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.
- Predicate Logic (slides)
- 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.
- 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.
- The Predicate Calculus
We present the predicate calculus in the form of a natural deduction
system for the predicate logic.
Bibliography
- J.E. Hopcroft & R. Motwani & J.D. Ullmann - Introduction to Automata Theory, Languages
and Computation - Pearson International Edition, 2007