v2.11.0 (5648)

# Cours scientifiques - CSE206 : Introduction to Formal Languages

## Descriptif

`We introduce different concepts from automata theory and formal languages, including grammars, deterministic and non-deterministic automata, regular expressions and languages, and context-free languages. We approach computability through the a very simple model: the BitFlip language, whose abstract machine is simulated by an unrestricted grammar.`

## Objectifs pédagogiques

Students are expected to acquire, at least, an intuitive understanding of the concepts so that they can easily deal with standard examples.

## Pour les étudiants du diplôme Bachelor of Science de l'Ecole polytechnique

Vous devez avoir validé l'équation suivante : UE CSE203

Numérique sur 20

## Pour les étudiants du diplôme Bachelor of Science de l'Ecole polytechnique

Le rattrapage est autorisé (Note de rattrapage conservée écrêtée à une note seuil de 10)
L'UE est acquise si Note finale >= 10
• Crédits ECTS acquis : 3 ECTS

La note obtenue rentre dans le calcul de votre GPA.

## Pour les étudiants du diplôme Echanges PEI

Le rattrapage est autorisé (Note de rattrapage conservée écrêtée à une note seuil de 10)

### Programme détaillé

```1)
Grammars and Formal Languages :
Operations on languages,
Rewriting,
Grammars,
Two important classes of grammars

2)
Regular Languages and Finite State Automata :
Finite state automaton,
Regular languages vs Finite Automata,
The pumping lemma,
Deciding emptiness and finiteness

3)
Regular expressions :
The language of Regular expressions,
Interpretation of Regular expressions,
The Kleene theorem Proof of the Kleene theorem
From Regular expressions to Automata

4)
Proof of the Kleene theorem (continued) :
Generalised finite automata,
The Brzozowski - McCluskey state elimination procedure
The star-height problem
Deterministic finite automata :
The powerset construction,
Completion,
Adding the complement operator to regular expressions

5)
Smallest deterministic finite automata :
The Myhill - Nerode theorem,
The Moore algorithm,
The Brzozowski's algorithm

Lexing

6)
Context-Free languages:
Basic transformations,
Chomsky normal forms,
Weak pushdown automata,
The pumping lemma,
Eliminating left-recursiveness

7)
The BitFlip language :
Syntax and Semantics

Interpretation as an unconstrained grammar :
Rules and Facts
```

### Mots clés

Formal Languages, Regular Expressions, Context-Free Languages, Myhill - Nerode, Kleene, Brzozowski - McCluskey