Télécharger cours informatique en PDF Cours informatique PDF 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:
