Langages rationnels

Notations et définitions :

• on note en général \(\Sigma\) l'alphabet considéré, un ensemble fini de symboles (souvent \(a,b,c,\ldots\)) ;
• si \(\Sigma\) est un alphabet, on note \(\Sigma^*\) l'ensemble de tous les mots formés des symboles de \(\Sigma\), en incluant notamment le mot vide \(\varepsilon\) ;
• si \(L\) et \(M\) sont des langages (des sous-ensembles de \(\Sigma^*\)) :
  • \(L.M=LM\) est l'ensemble des mots constitués d'un mot de \(L\) suivi d'un mot de \(M\) ;
  • \(L|M=L\cup M\) est l'union des langages, c'est-à-dire l'ensemble des mots soit dans \(L\) soit dans \(M\) ;
• si \(L\) est un langage :
  • \(L^0=\{\varepsilon\}\) ;
  • \(L^1=L\) ;
  • \(L?=L|L^0\) ;
  • \(L^{k+1}=L.L^{k}=L^{k}.L\) ;
  • \(L^+=\bigcup_{k\geq 1}L^k\) ;
  • \(L^*=\bigcup_{k\geq 0}L^k\).
• pour tout mot \(w\in \Sigma^*\), on note par simplification \(w\) le langage réduit au mot \(w\) seul, c'est-à-dire le langage \(L=\{w\}\).