%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt,a4paper]{article}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
%\usepackage{ucs}
\usepackage{times}
% A tribute to the worthy AMS:
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
%
\usepackage{mathrsfs}
\usepackage{wasysym}
\usepackage{url}
%
\usepackage{graphics}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}
\usetikzlibrary{matrix}
%
\theoremstyle{definition}
\newtheorem{comcnt}{Tout}
\newcommand\thingy{%
\refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} }
\renewcommand{\qedsymbol}{\smiley}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
%
\DeclareUnicodeCharacter{00A0}{~}
%
\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
%
%
%
\begin{document}
\title{THL (Théorie des langages)\\Programme du cours}
\author{David A. Madore}
\maketitle

\centerline{\textbf{INF105}}

{\footnotesize
\immediate\write18{sh ./vc > vcline.tex}
\begin{center}
Git: \input{vcline.tex}
\end{center}
\immediate\write18{echo ' (stale)' >> vcline.tex}
\par}


%
%
%

\thingy Présentation générale.  Alphabet, mots, langages.  Opérations
et notions sur les mots : concaténation de deux mots, longueur d'un
mot ; préfixe, suffixe, facteur, sous-mot et mot miroir.

Opérations sur les langages : opérations booléennes (complémentaire,
union, intersection), concaténation, étoile de Kleene.

\thingy  Définition des langages rationnels.  Expressions rationnelles.

Automates finis : automates déterministes (DFA), automates
déterministes à spécification incomplète (DFAi), automates non
déterministes (NFA), automates non déterministes à transitions
spontanées ($\varepsilon$-NFA).

\thingy Équivalence entre DFA, DFAi, NFA et $\varepsilon$-NFA.
Langages reconnaissables.

Stabilité des langages reconnaissables par complémentaire,
union, intersection ; stabilité par concaténation et étoile de Kleene.

Les langages rationnels sont reconnaissables.  Automate de Glushkov
\emph{ou} (au choix) automate de Thompson d'une expression
rationnelle.

\thingy Automates à transitions étiquetées par des expressions rationnelles
(informellement), équivalence avec les autres sortes d'automates,
équivalence avec les expressions rationnelles (par élimination des
états =algorithme de Kleene).  Équivalence entre langages rationnels
et reconnaissables.

Énoncé et démonstration du lemme de pompage pour les
langages rationnels (=reconnaissables).

\thingy Exemples d'utilisation du lemme de pompage.

DFA minimal\footnote{On conviendra d'utiliser la notion d'automate
  déterministe \emph{complet}, et la première étape de minimisation
  sera de compléter l'automate en lui ajoutant éventuellement un
  puits.} (=canonique).  Algorithme de minimisation (=algorithme de
Moore).  (On insistera plus sur l'aspect algorithmique que sur la
formulation théorique du théorème de Myhill-Nerode.)  Conséquence : on
peut décider algorithmiquement si deux expressions rationnelles sont
équivalentes.


\thingy TD sur les automates finis et langages rationnels.


\thingy Grammaires hors contexte, langages algébriques (=définis par
une grammaire hors contexte).  Dérivations\footnote{On pourra même
  sauter complètement la notion de dérivation et définir le langage
  engendré par une grammaire à travers les arbres d'analyse.}.  Arbre
d'analyse (=de dérivation).  Ambiguïté (grammaires inambiguës et
ambiguës).

Stabilité des langages algébriques par réunion, concaténation
et étoile de Kleene.  Les langages rationnels sont algébriques :
d'après ce qu'on vient de dire et directement en associant une
grammaire à un DFA ou NFA.

L'intersection d'un langage algébrique et d'un langage
rationnel est algébrique (admis sans démonstration).

L'appartenance d'un mot au langage défini par une grammaire hors
contexte est algorithmiquement décidable (admis sans démonstration).


\thingy Éléments de calculabilité\footnote{Mieux vaut sans doute ne pas
  perdre de temps à introduire un modèle de calculabilité particulier
  (machine de Turing ou fonctions générales récursives, par exemple) :
  insister sur le fait que tout langage de programmation raisonnable,
  suffisamment idéalisé, est équivalent.} : algorithme, terminaison
d'un algorithme, thèse de Church-Turing.

Ensembles/langages\footnote{Souligner qu'ici contrairement au reste du
  cours, on peut indifféremment considérer des ensembles d'entiers
  naturels ou de mots.} décidables (=calculables, =récursifs) et
semi-décidables (=semi-calculables, =récursivement énumérables).  Un
ensemble est décidable ssi lui et son complémentaire sont
semi-décidables.  Un ensemble est semi-décidable ssi il est (vide ou)
énuméré par une fonction calculable.

\thingy Notion de machine universelle.  Indécidabilité du problème de l'arrêt.

\thingy TD sur les grammaires hors contexte / langages algébriques, et
sur la calculabilité.


%
%
%
\end{document}