Ce cours pdf présente quelques concepts fondamentaux de la théorie des langages formels. La combinatoire des mots étudie les propriétés des suites de symboles.
Plan du cours
- Les mots et les langages
- Définitions
- Les expréssions réguliers
- Les automates
- Les automates détérministes et les automates non détérministes
- Langages réguliers et automates
- Stabilité de la régularité
- Critére de non-régularité
- Exercices et applications
- Automate minimal
- Construction de l’automate minimal
- Monoide syntaxique
- Les formes normales
- Grammaires et langages réguliers
Profitez de ce manuel de formation en PDF pour comprendre mieux le automate et enrichir votre connaissance.
Commencez à télécharger ce cours adapté pour vous et à apprendre automate.
6ChapitreI.Mots etlangagesave cx non vide, alors ilexiste desmots u;vet un entier k 0tels quex = uv ;y= (uv )ku = u(v u )ket z= vu:D emonstration. Sijx j jy j, alors nousav ons lasituation suivante. Ainsi, y yxzyv FigureI.2.xy=yz, jx j jy j.il existe unmot vtel que x= yv (si jx j= jy j, alors v= « ). Dans cecas, onp eut prendre u= yet k= 0.Si 0< jx j < jy j, on procede parrecurrence surjy j. Si jy j = 2etj x j= jz j = 1, on axy1 y2 =y1 y2 z; x;z;y1;y2 2et on endeduit quex= y1 =y2 =z. Donc, u= y1,v = "et k= 1con viennen t.Supp osons a presen tla propri et e satisfaite pour jy j netv erions-la pour jy j = n+ 1. Puisque jx j < jy j, il existe unmot wtel que x yy zx w Figure I.3.xy=yz, jx j< jy j.y = xw .Ainsi, xy=yz se re ecritxxw =xw z:De la, on tire xw=wz av ec jw j 0. Soit jx j jw jet onapplique lapremi ere partie delapreuv e,soit jx j < jw jet on peut des lorsappliquer l'hyp oth ese derecurrence :il existe desmots u;vet un entier ktels quex= uv ;w = (uv )ku = u(v u )ket z= vu:P our conclure, onremarque quey = xw =uv (uv )ku = (uv )k+1u:D enition I.1.21 .Soit w= w1 w` unmot, av ec wi2 pour tout i.L'en tierk 1est une perio dede wsiw i=wi+ k;8i = 1;::: ;` k: