Le but de cet exercice est de présenter plusieurs opérations stables sur les langages rationnels. On suppose connu l’équivalence entre les langages rationnels et les langages reconnaissables par automate fini.
Exercice
Soit L1 et L2 deux langages rationnels sur l’alphabet Σ. Montrer que les langages suivants sont rationnels.
1) ¯L1=w∈Σ∗|w∉L1 le complémentaire de L1.
2) L1∩L2 l’intersection de L1 et L2.
3) L1∖L2 la différence ensembliste de L1 et L2.
4) Mir(L1)={ˉw=w1w2…wn∈Σ∗|wi∈Σ,w=wn…w2w1∈L1} le langage miroir de L1.
5) Pre(L1)={w∈Σ∗|∃v∈Σ∗,wv∈L1}, le langage des préfixes de L1.
6) Suf(L1)={w∈Σ∗|∃u∈Σ∗,uw∈L1}, le langage des suffixes de L1.
7) Fac(L1)={w∈Σ∗|∃u,v∈Σ∗uwv∈L1}, le langage des facteurs de L1.
8) L1#L2 : le produit mélangé de L1 et L2. Les mots mélangé sont les u1v1…ukvk avec les ui,vi∈Σ∗, avec u=u1u2…uk∈L1 et v=v1v2…vk∈L2.
9) √L1={w∈Σ∗|ww∈L1}, la racine carré de L1.
10) L12={w∈Σ∗|∃u∈Σ∗,|w|=|u|,wu∈L1,}, la moitié de L1.
Correction
Dans toute la suite, on notera A1=(Σ,Q,q0,F,δ) et A2=(Σ,Q′,q′0,F′,δ′) deux automates déterministe complet reconnaissant respectivement L1 et L2.
1) Un mot w appartient à L1 si et seulement si on atteint un état de F dans A1 lorsqu’on lit w. De ce fait, un mot n’est pas dans L1 si et seulement si on atteint un état de Q∖F dans A1 lorsqu’on lit w. Il en résulte donc que le complémentaire de L1 est reconnu par l’automate : ¯A1=(Σ,Q,q0,Q∖F,δ)
2) Pour deux ensembles A et B on rappel qu’on a la formule suivante : A∩B=¯¯A∪¯B
3) On rappel que pour deux ensembles A et B on a : A∖B=A∩¯B
4) On considère δ−1 la fonction qui à (q,a)∈Q×Σ associe l’ensemble, éventuellement vide, des états q′ de Q tels que δ(q,a)=q′. On veut montrer que Mir(L1) est reconnu par l’automate non déterministe suivant : Mir(A1)=(Σ,Q,F,{q0},δ−1)
5) Soit T l’ensemble des états q de A1 tel qu’il existe un chemin de q vers un état de F. Soit vq le mot formé par ce chemin. On considère un mot w tel que A1 arrive dans un état q de T lorsqu’il le lit. On note alors que si on lit wvq on arrive dans un état de F. Il en résulte que wvq∈L1 Donc w∈Pre(L1). De plus, si w est un mot préfixe de L1 alors il existe v tel que wv∈L1. Donc, si A1 arrive dans un état q en lisant w alors q∈T. Il en résulte que Pre(L1) est reconnu par l’automate suivant : Pre(A1)=(Σ,Q,q0,T,δ)
6) On note que le langage des suffixes de L1 est le miroir du langage des préfixes de Mir(L1). Il en résulte donc que le langage des suffixes d’un langage rationnel est un langage rationnel.
7) On remarque que les facteurs d’un mot correspond à l’ensemble des préfixes de ses suffixes. On a donc : Fac(L1)=Pre(Suf(L1))
8) On pose Δ une fonction de (Q×Q′)×Σ dans P(Q×Q′) l’ensemble des parties de Q×Q′ et définie par : Δ((q,q′),a)={(r,q′)|δ(q,a)=r}⋃{(q,r′)|δ′(q′,a)=r′}
9) Le principe de l’automate qu’on va construire ici est de simuler la lecture de notre mot d’entrée en partant de tous les états à la fois. Ainsi, une fois qu’on aura terminer de lire notre mot, on pourra directement le lire une seconde foi. L’ensemble d’états qui nous intéresse est donc Qn où n est le nombre d’états de l’automate. Notre état initial est (q0,q1,…,qn−1) où les qi sont les états de Q numérotés de 0, l’état initial, à n. Notre fonction d’état δn est donnée par : δn((p0,…,pn−1),a)=(δ(p0,a),…,δ(pn−1,a))
10) On procède de même que pour la racine carrée excepté qu’on utilise un automate non déterministe. Cette fois-ci, on s’intéresse à tous les états accessible à partir de chaque état. Notre automate a pour ensemble d’état Qn+1. Notre fonction d’état δn+1 est donnée par : δn+1((p,p0,…,pn−1),a)={(δ(p,a),δ(p0,x1),…,δ(pn−1,xn)|∃x1,…,xn∈Σ}