SAVOIRS
Langages rationnels
Des automates dans tous leurs états
Un mo t étant do nné, o n pe ut se de ma nde r s' il fa it pa rtie o u no n d ' un la ngage .
Po ur ce la, il ex iste une mac hine a bstraite (appelée automate fini), composée
d ' un no mbre fini d 'états re liés par des
fl èches é tique tées pa r des le ttres. Les
a uto ma tes déterm inistes n 'o nt qu ' un
seul état initia l et une unique fl èche é ti -
quetée par une le ttre pour c haque état.
Pour tester un mot , il fa ut partir de ! 'état
initi al e t sui vre les fl èches corres po ndant aux lettres du mot les unes après les
a utres. Si l'automate est déte rmini ste,
il ne possède qu ' un état initial et il ex iste,
à c haque é tape, au plus une fl èche é ti -
que tée par chaque lettre. Le che min (on
dit a uss i calcul) ainsi construit à partir
d ' un mot sur un automate dé te rmini ste
est donc unique . Après avo ir é puisé les
lettres du mot , s i on se trouve sur un
état fin al, le mot est accepté, sinon il est
rejeté par l'automate. Le langage reconnu
par cet automate est l'ensemble des mots
acceptés par cet automate. Dans le même
ordre d'id ées, un lan gage es t reconnaissable s' il existe un automate qui le
reconnaît. De maniè re remarqua ble, un
b
Un automate qui reconnaît le langage b(ab + b)*.
Par exemple, pour tester bba, on part de l'état initial O
(i ndiqué par la flèche entrante). La flèche étiquetée par b
nous mène en 1, la flèche suivante nous laisse en 1 et on finit
enfin en 2, qui n'est pas un état final : le mot est donc rejeté.
Le mot a est directement rejeté. Le mot bbab, en revanche ,
fait arriver en 1, qui est final (indiqué par la flèche sortante),
donc le mot est accepté. Et en effet, le langage dénoté
par b(ab + b)* contient bbab mais pas bba.
la ngage est reconna issab le si , e t seu lement si , il est rationnel. C'est le théorème
de Kl eene , dont il ex iste un e pléthore
de démonstrations.
En particulier, pour c haq ue express io n
rati o nne lle o n peut construire un automa te qui reco nn aît le la ngage dé noté
par cette ex press io n . Une intuiti o n pour
compre nd re po urquo i
{a"b" , avec n un e nti er q ue lco nqu e}
n 'est pas rat io nne l est de remarquer que
les é tats d ' un a utomate pe uve nt renfermer un e info rmation bornée. Or, pour
accepter un mot de ce la ngage , lorsqu 'o n a lu un no mbre arb itra ireme nt
grand de a, o n a beso in de vé rifier qu'il
y a auta nt d'occurrences de b.
Pour compte r les occurre nces du mot
chaton da ns un texte, o n peut construire
un auto m ate qui reco nnaît le langage
rationnel A *chaton (les mots qui finissent par chaton) sur l'a lph abet nat ure l,
qui pe ut lire le tex te à trave rs l' autom a te e t in c ré m e nte r un co mpte ur à
c haque fois que l'on visite un état final
(qui correspo ndra à une occurre nce de
chaton dans le tex te).
On pe ut auto ri ser un automate à posséde r plu sie urs c he min s étiquetés par un
mot. On obtient ce qu 'o n a ppe ll e un
automate non déterministe e t un mot est
accepté si au moins un des chemins qu'il
étique tte est acceptant, rejeté si no n .
Bonn e no uv e ll e, il es t poss ibl e de
construire pour c haque a uto mate no n
dé te rmini ste un automate détermini ste
qui reconn aît le mê me la ngage ! Mauvaise nouve lle, l'automate ainsi constrn it
pe ut avo ir ex po ne nti e ll e m e nt plus
d 'états . .. Ces de ux classes d 'auto mates
ont do nc é to nna mme nt le même pouvoir ex press if : il s sont éq ui va lents en
ce qu ' il s sont capables de ca lcul e r, mais
ils diffèrent dans la manière dont il le calc ul e nt. Il fa ut tro uve r un co mp rom is
e ntre le fa ible no mbre d 'états des autoTangente Hors-série n°52. Mathématiques & informatique
Langages rationnels
Des automates dans tous leurs états
Un mo t étant do nné, o n pe ut se de ma nde r s' il fa it pa rtie o u no n d ' un la ngage .
Po ur ce la, il ex iste une mac hine a bstraite (appelée automate fini), composée
d ' un no mbre fini d 'états re liés par des
fl èches é tique tées pa r des le ttres. Les
a uto ma tes déterm inistes n 'o nt qu ' un
seul état initia l et une unique fl èche é ti -
quetée par une le ttre pour c haque état.
Pour tester un mot , il fa ut partir de ! 'état
initi al e t sui vre les fl èches corres po ndant aux lettres du mot les unes après les
a utres. Si l'automate est déte rmini ste,
il ne possède qu ' un état initial et il ex iste,
à c haque é tape, au plus une fl èche é ti -
que tée par chaque lettre. Le che min (on
dit a uss i calcul) ainsi construit à partir
d ' un mot sur un automate dé te rmini ste
est donc unique . Après avo ir é puisé les
lettres du mot , s i on se trouve sur un
état fin al, le mot est accepté, sinon il est
rejeté par l'automate. Le langage reconnu
par cet automate est l'ensemble des mots
acceptés par cet automate. Dans le même
ordre d'id ées, un lan gage es t reconnaissable s' il existe un automate qui le
reconnaît. De maniè re remarqua ble, un
b
Un automate qui reconnaît le langage b(ab + b)*.
Par exemple, pour tester bba, on part de l'état initial O
(i ndiqué par la flèche entrante). La flèche étiquetée par b
nous mène en 1, la flèche suivante nous laisse en 1 et on finit
enfin en 2, qui n'est pas un état final : le mot est donc rejeté.
Le mot a est directement rejeté. Le mot bbab, en revanche ,
fait arriver en 1, qui est final (indiqué par la flèche sortante),
donc le mot est accepté. Et en effet, le langage dénoté
par b(ab + b)* contient bbab mais pas bba.
la ngage est reconna issab le si , e t seu lement si , il est rationnel. C'est le théorème
de Kl eene , dont il ex iste un e pléthore
de démonstrations.
En particulier, pour c haq ue express io n
rati o nne lle o n peut construire un automa te qui reco nn aît le la ngage dé noté
par cette ex press io n . Une intuiti o n pour
compre nd re po urquo i
{a"b" , avec n un e nti er q ue lco nqu e}
n 'est pas rat io nne l est de remarquer que
les é tats d ' un a utomate pe uve nt renfermer un e info rmation bornée. Or, pour
accepter un mot de ce la ngage , lorsqu 'o n a lu un no mbre arb itra ireme nt
grand de a, o n a beso in de vé rifier qu'il
y a auta nt d'occurrences de b.
Pour compte r les occurre nces du mot
chaton da ns un texte, o n peut construire
un auto m ate qui reco nnaît le langage
rationnel A *chaton (les mots qui finissent par chaton) sur l'a lph abet nat ure l,
qui pe ut lire le tex te à trave rs l' autom a te e t in c ré m e nte r un co mpte ur à
c haque fois que l'on visite un état final
(qui correspo ndra à une occurre nce de
chaton dans le tex te).
On pe ut auto ri ser un automate à posséde r plu sie urs c he min s étiquetés par un
mot. On obtient ce qu 'o n a ppe ll e un
automate non déterministe e t un mot est
accepté si au moins un des chemins qu'il
étique tte est acceptant, rejeté si no n .
Bonn e no uv e ll e, il es t poss ibl e de
construire pour c haque a uto mate no n
dé te rmini ste un automate détermini ste
qui reconn aît le mê me la ngage ! Mauvaise nouve lle, l'automate ainsi constrn it
pe ut avo ir ex po ne nti e ll e m e nt plus
d 'états . .. Ces de ux classes d 'auto mates
ont do nc é to nna mme nt le même pouvoir ex press if : il s sont éq ui va lents en
ce qu ' il s sont capables de ca lcul e r, mais
ils diffèrent dans la manière dont il le calc ul e nt. Il fa ut tro uve r un co mp rom is
e ntre le fa ible no mbre d 'états des autoTangente Hors-série n°52. Mathématiques & informatique