1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
|
%% 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 indicatif}
\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. Définition des
langages rationnels. Expressions rationnelles.
\thingy Automates finis : automates déterministes (DFA), automates
déterministes à spécification incomplète, automates non déterministes
(NFA), automates non déterministes à transitions spontanées
($\varepsilon$-NFA).
Équivalence entre ces différentes sortes d'automates. Langages
reconnaissables.
\thingy Stabilité des langages reconnaissables par complémentaire,
union, intersection ; stabilité par concaténation et étoile de Kleene.
Les langages rationnels sont reconnaissables. Automate de Thompson.
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). Équivalence entre langages rationnels et reconnaissables.
\thingy Énoncé et démonstration du lemme de pompage pour les
langages rationnels (=reconnaissables).
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.
\thingy TD sur les automates finis.
\thingy TP sur les expressions régulières et automates finis.
\thingy Grammaires hors contexte\footnote{Je propose pour gagner du
temps de ne faire que mentionner au passage le fait qu'il existe des
grammaires plus générales, sans entrer dans les détails.}, langages
algébriques (=définis par une grammaire hors contexte). Dérivations,
dérivations gauches et droites. Arbre d'analyse (=de dérivation).
Ambiguïté (grammaires inambiguës et ambiguës, exemple de langage
intrinsèquement ambigu).
\thingy 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).
Énoncé du lemme de pompage pour les langages algébriques.
(Selon le temps disponible.) L'appartenance d'un mot au langage
défini par une grammaire hors contexte est algorithmiquement
décidable\footnote{Par ex., esquisser comment on peut mettre la
grammaire sous forme normale de Chomsky et utiliser l'algorithme de
programmation dynamique (CYK) ?}. Quelques notions sur l'analyse
syntaxique en pratique : notion d'analyseurs descendants et
ascendants.
\thingy TD sur les grammaires hors contexte.
\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.
Notion de machine universelle. Indécidabilité du problème de l'arrêt.
\thingy TP sur les grammaires hors contexte avec JavaCC.
%
%
%
\end{document}
|
