0°) Motifs "shell"

ls *.c ⇒ affiche la liste des fichiers dont le nom se termine par ".c"
* "jocker" ⇒ n'importe quelle chaîne
[a b c] ⇒ soit a, soit b, soit c = [a - c]
[! a b c] ⇒ un caractère, sauf a, b ou c
remarque: on ne peut pas faire tout ce qu'on veut avec le motifs.
ex: tous les fichiers "projet-___.zip" avec "___" étant un nombre -> impossble

1°) Expression régulières

une expression régulière désigne un ensemble de chaînes de caractèes et utilise les symboles suivants:
  • . : un caractère quelconque sauf "\n"
  • [a b c d] : un caractère parmit la liste
  • [^ a b c d] : un caractère sauf ceux mentioné dans la liste
  • expr* : l'expression "expr" répétée autemps de fois que l'on veut
  • expr+ : l'expression "expr" répétée au moin une fois
  • ^ $ : début et fin de ligne
  • ( ) : pour grouper des expressions
  • \w : n'importe quel caractère alphanumérique
  • \d : chiffre de 0 à 9
  • \s : whitespace
  • \1 : référence vers le groupe 1
  • \2 : référence vers le groupe 2, ...etc

2°) Expression de Kleene

Pour étudier les regex, on utilise une version simplifiée
définition: les regex de Kleene sont données par la grammaire "R ::= 0 | 1 | R+R | R.R | R* | (R) | s"
alphabet ⇒ ensemble fini de symboles
mot ⇒ suite finie de symboles de Σ
mot sur Σ ⇒ suite finie de symboles de Σ
w.w ⇒ concaténation de deux mots w
langage sur Σ, c'est un ensemble de mot ( Σ={a,b,c} ⇒ L=rêgle )

si R est une regex sur Σ, L(R), le langage reconnu par R, est défini par:

L(0) = 0
L(1) = ε
L(s) = s
L(R1+R2) = L(R1) ⋃ L(R2)
L(R1.R2) = { w | w = w1.w2 avec w1 ∈ L(R1) et w2 ∈ L(R2) }
L(R*) = { w | w = w1.w2.∞.wn avec n ≥ 0 et chaque wi ∈ L(R) }