Langages réguliers et hors-contexte
Cours M1 INaLCO, 2013-2014
Plan de marche du 2nd semestre
-
30/01 : Retour sur l'examen de janvier
- Corrigé
- Autre exemple de décodage d'entités-caractères (texte
tibétain).
Voici le
script que nous avons écrit en cours.
Remarque : quand on applique ce script au fichier que voici, les
deux premières lignes du fichier-résultat sont identiques.
Pouvez-vous expliquer pourquoi ?
le 6/02 : pas de cours (séminaire au Quai Branly)
-
13/02 : Bilan sur les expressions régulières en Perl
-
- Notion générale de grammaire (système de réécriture)
et d'automate (machine de Turing)
- Idée des hiérarchies parallèles de grammaies et d'automates
- Grammaires context-sensitive, automates linéairement bornés
27/02 : Vacances de neige
-
- Règles sans contexte, exemples & non-exemples
- Propriétés de fermeture
- Automates à pile
- Grammaires linéaires unilatères et langages réguliers
-
- Arbres de dérivation
- Ambiguïté
- L'ambiguïté due aux séquences
- Grammaires classiques pour les expressions arithmétiques
-
- Les deux analyseurs canoniques
- Rendre l'un d'entre eux déterministe.
-
27/03 : Analyseurs descendants en C++
-
03/04 : Analyseurs ascendants en C++
-
10/04 : Synthèse
17 & 24/04 Vacances de printemps
01/05 : Fête du travail
08/05 : Commémoration de la victoire de 1945
- 15/05 : Bilan
Examen entre le 19 et le 31/05
Plan de marche du 1er semestre
N.B. Le plan de marche ci-après reproduit celui de l'année
dernière.
Il sera mis à jour chemin faisant...
Les modifications seront anoncées sur le
fil RSS du cours, auquel vous êtes invités à vous abonner.
Cours n° 1, 26
septembre
2013 : Expressions et ensembles
- Notion d'expression en général : expressions arithmétiques,
expressions régulières
- La valeur d'une expression régulière est un ensemble (en
général)
infini
- Problème de l'infini en puissance et en acte
- Ensembles en extension et en compréhension
- Appartenance et inclusion
Cours n° 2, 3
octobre 2013 :
Ensembles de
mots : langages
- Opérations ensemblistes, lois sur les opérations ensemblistes
- Les mots et leur concaténation
- Opérations spécifiques sur les ensembles de mots
- Expressions régulières
Cours n° 3, 10 octobre
2013 : Réflexions
diverses sur les expressions régulières
- Rôle des expressions régulières : exemples
"concrets".
- Langages réguliers
- Fermeture, Extensions
- Syntaxes
Cours n° 4, 17 octobre
2013 : Automates
finis déterministes
- Notion d'automte fini et de langage reconnu par un automate
- Automate minimal
- Processus de réduction
- Remarque : en analysant l'automate "exemple scolaire",
nous avons directement abouti à l'e.r.
b*a(ab*a)*b(bb)*
,
qui reflète exactement la structure de l'automate minimal
correspondant.
Cet automate ayant été construit pour reconnaître le langage valeur de
l'e.r. (aa | b)*ab(bb)*
,
nous tirons de cette expérience un nouvel exemple d'égalité entre les
langages décrits par deux e.r. différentes :
b*a(ab*a)*b(bb)* =
(aa | b)*ab(bb)*.
Cours n° 5, 24 octobre
2013 : Automates
finis non-déterministes
- Notion d'automate fini non-déterministe et de langage reconnu
par
un tel automate
- Construction d'un automate fini déterministe
équivalent à
un automate fini non-déterministe
- Propriétés de fermeture des langage reconnus par automates
finis
- Tout langage régulier peut être reconnu par un automate fini
- Critère pour établir qu'un langage n'est pas régulier (lemme
de
l'étoile)
--------- Vacances d'automne
Cours n° 6, 7
novembre 2013 : Équivalence
e.r. - automates finis
- Construction d'un automate non-déterministe à partir d'une e.r.
- Construction d'une e.r. à partir d'un automate (McNaughton
&
Yamada)
- Théorème de Kleene
Cours n° 7, 14
novembre
2013 : Mise en œuvre par programme
- Représentation d'un automate en XML
- Traduction en un programme C++
- Autres façons de faire fonctionner un automate traduit en C++
Cours n° 8, 21
novembre
2013 : Expressions régulières en Perl 1
- Contexte de mise en œuvre
- Le cas de Perl
- Premiers exemples
Cours n° 9, 28 novembre 2013 : Interrogation écrite
Cours n° 10, 5 décembre 2013 :
Retour sur l'interrogation
écrite
Cours n° 11, 12
décembre
:
Au lieu de Expressions régulières en Perl 2, exposé impromptu
sur RDF, SPARQL, DBPédia et
OWL,
à partir des notes du cours XML de M2-IM.
NB : le problème de syntaxe rencontré en écrivant la requête pour
DBPedia
PREFIX dbpedia-owl: <http://dbpedia.org/ontology/>
select ?bp ?dp where {
{<http://dbpedia.org/resource/Mary_Shelley> <dbpedia-owl:birthPlace>
?bp }
UNION
{<http://dbpedia.org/resource/Mary_Shelley> <dbpedia-owl:deathPlace>
?dp }
}
se résout en supprimant les chevrons autour des relations :
PREFIX dbpedia-owl: <http://dbpedia.org/ontology/>
select ?bp ?dp where {
{<http://dbpedia.org/resource/Mary_Shelley>
dbpedia-owl:birthPlace ?bp }
UNION
{<http://dbpedia.org/resource/Mary_Shelley>
dbpedia-owl:deathPlace ?dp }
}
Essayez !
Cours n° 12, 19
décembre : Expressions régulières en Perl 2
- Sous-expressions parenthésées
- Les suffixes
g
(global) et e
(evaluate)
- Voir aussi Cours15.
Vacances de
Noël
Cours n° 13, 9 janvier
2014 : Expressions régulières en Perl 3
- "Quantificateurs"
- Classes de caractères
- Ancres