Examen INF232 2013 (corrigé de Michaël Périn)

Exercice 1

VRAI: -> (1)-Sigma-> (1) est déterministe et complet, il reconnaît le langage {} puisqu'il n'a pas d'état accepteur.
FAUX: Prenons L = {a} alors L* = {a}* n'est pas contenu dnas L puisque aa in L* et que aa not in L.
FAUX: Prenons L=Sigma* alors L* = (Sigma*)* = Sigma*/ donc L=L* et donc L n'est pas strictement inclus dans L*.
VRAI: Je suppose qu'on considère deux automates qui reconnaissent le même langage. Dans ce cas, si l'un des automates a moins d'états que l'autre, c'est que l'autre n'est pas minimal puisque la minimisation consiste à regrouper les états équivalents.
FAUX: Contre-exemple : les deux automates ->((1))-a->((1)) et ->((1))-a->((1))-b->(2) reconnaissent le langage {a}*, sont déterministes et n'ont pas le même nombre d'états.
VRAI: Il y a équivalence puisqu'on peut passer des expressions régulières aux automates minimaux par la méthode de Thompson puis l'élimination des epsilon-transitions puis la déterminisation puis la minimisation et inversement on peut passer des automates minimiaux aux expressions régulières par résolution des équations d'Arden associées à l'automate.
FAUX: La correction partielle ne traite pas de la terminaison, elle l'a suppose en quelque sorte puisqu'elle consiste à prouver que « lorsque l'exécution atteint l'état q_t alors la propriété associée à q_t est satisfaite ».
VRAI: pour tout x<0 dans Z, on peut choisir un y dans N tel que x+y>0 ; il suffit de choisir y=x+1.

Exercice 2

On considère l'automate donné sous forme de tableau, il suffit alors de parcourir les cases du tableau pour vérifier qu'elles contiennent au plus une valeur (éventuellement aucune).
Étant donnés deux automates A1 et A2 on cherche un algorithme qui permet de déterminer si Lang(A1)* est inclus dans Lang(A2). Pour cela, on procède en deux étaptes : (a) on construit un automate K1 qui reconnait Lang(A1)* puis (b) on teste l'inclusion des langages Lang(K1) inclus? Lang(A2)
(a). pour construire K1 on prend l'automate A1 auquel on ajoute une espilon-transition de tout état accepteur vers tout état initial et on rend accepteur les états initiaux.

(b). Rappelons qu'un ensemble E est inclus dans F si et seulement si E inter comp(F) est vide. Donc pour (b) il nous faut tester si K1 x comp(A2) reconnaît le langage vide. On construit donc le produit K1 x comp(A2) puis on vérifie qu'aucun état accepteur n'est accessible depuis l'état initial.

Exercice 4

a².b⁴ appartient à L ainsi que a.bⁿ. Par contre b.a n'appartient pas à L ni aⁿ.bⁿ⁺¹
Si L était régulier alors il devrait satisfaire le critère de régularité. Pour montrer que L est irrégulier, on va donc montrer que L ne satisfait pas le critère de régularité. Autrement dit,
/Pour tout n,/

on peut trouver un mot w de L : on prend w = aⁿ.bⁿ il appartient à L car n divise n

de taille >= n : |w|=2n >= n

tel que pour tout choix de x,y,z avec w=x.y.z et |x.y| <=n et |y|>0 : w s'écrit donc a^X . a^Y. a^Z .bⁿ avec x = a^X, y = a^Y, z = a^Z.bⁿ et Y>0 et X+Y+Z=n

on peut trouver un k de N tel que x.y^k.z not in L

Pour montrer que x.y^k.z not in L il faut montrer que
- |x.y^k.z|_a ne divise pas |x.y^k.z|_b
- ie. X + k.Y + Z ne divise pas n
- ie. X + Y + Z + (k-1) Y ne divise pas n
- ie. n + (k-1) Y ne divise pas n
- il suffit donc de trouver un k tel que n + (k-1) Y > n
- ie. tel que (k-1) Y > 0
Finalement, puisque Y>0 il suffit de choisir k tel que k-1>0 ie. k>1.

Exercice 5

On remarque que la variable b n'est jamais modifié au cours du programme on peut donc la considèrer comme une constante qu'on notera B

On considère donc le programme suivant

c:= B; p:= 0 ; while (c>0){ p:=p+B ; c:=c-1 }

Question 1.

A = (Sigma,Q,I,F,Delta) avec

Q = {q₀,q₁,q₂,q_t},
I = q₀,
F = {q_t},
Sigma = {"c:=B;p:=0", "c>0" , "c<=0" , "p:=p+B;c:=c-1"},
Delta = { (q₀, c:=B;p:=0, q₁) , (q₁,c<=0,q_t) , (q₁,c>0,q₂) , (q₂,p:=p+B;c:=c-1,q₁) }

Question 4.

On choisit d'associer la propriété P_t := p = B² /\ c=0 à l'état q_t

La transition (q₁,c<=0,q_t) nous permet de choisir la propriété P₁ en q₁.

Soit s l'état de la mémoire en q₁ et s' l'état de la mémoire en q_t, la propriété P₁ doit satisfaire l'implication :

[ P₁ /\ c<=0 ] en s ==> [ P_t ] en s'

or s'= s puisqu'un test ne modifie pas la valeur des variables, donc l'implication se réecrit

[ P₁ /\ c<=0 ==> P_t ] en s

[ P₁ /\ c<=0 ==> p = B² /\ c=0 ] en s

On choisit pour P₁ := (¹) B*c + p = B² /\ (²) c>=0

L'implication est satisfaite puisque:

test /\ (²) ==> c=0
c=0 (démontrée) /\ (¹) ==> p = B² (qu'on obtient en remplaçant c par 0 dans (¹))

La transition (q₂,p:=p+B;c:=c-1,q₁) nous permet de déterminer la propriété P₂ en q₂

Soit s l'état de la mémoire en q₂ et s'/ l'état de la mémoire en /q₁, la propriété P₂ doit satisfaire l'implication

[ P₂ ] en s ==> [ P₁ ] en s' avec s'(p) = s(p)+B , s'(c) = s(c)-1

[ P₂ ] en s ==> [B*c + p = B² /\ c>=0] en s'

[ P₂ ] en s ==> B * s'(c) + s'(p) = B² /\ s'(c)>=0

[ P₂ ] en s ==> B * (s(c)-1) + s(p)+B = B² /\ s(c)-1>=0

[ P₂ ] en s ==> [ B * (c-1) + p+B = B² /\ c-1>=0 ] en s

[ P₂ ==> B * (c-1) + p+B = B² /\ c-1>=0 ] en s

On choisit donc de prendre P₂ := (³) B * (c-1) + p+B = B² /\ (⁴) c-1>=0 et l'implication est trivialement satisfaite.

La transition (q₁,c>0,q₂) nous permet de vérifier nos choix de propriétés

Les propriétés P₁ en q₁ et P₂ en q₂ sont désormais fixées. Vérifions qu'elles satisfont l'implication

[P₁ /\ c>0] en s =?=> [ P₂ ] en s' avec s'=s

ie. [P₁ /\ c>0 =?=> P₂ ] en s

Autrement dit vérifions l'implication

(¹) B*c + p = B² /\ (²) c>=0 /\ [test] c>0 =?=> (³) B * (c-1) + p+B = B² /\ (⁴) c-1>=0

Preuve: . (³) se simplifie en B*c + p = B² et c'est exactement (¹) donc (¹) ==> (³) . puisque c est un entier, le test c>0 est équivalent à c>=1 ce qui démontre (⁴)

Enfin, la transition (q₀, c:=B;p:=0, q₁) nous permet de déterminser la pré-condition P₀ en q₀ du programme

Soit s l'état de la mémoire en q₀ et s'/ l'état de la mémoire en /q₁, la propriété P₀ doit satisfaire l'implication

[ P₀ ] en s ==> [ P₁ ] en s' avec s'(c) = B , s'(p) = 0

[ P₀ ] en s ==> [B*c + p = B² /\ c>=0] en s'

[ P₀ ] en s ==> B * s'(c) + s'(p) = B² /\ s'(c)>=0

[ P₀ ] en s ==> B * B + 0 = B² /\ B>=0

[ P₀ ] en s ==> [ B*B = B² /\ B>=0 ] en s

[ P₀ ==> B*B = B² /\ B>=0 ] en s

qui se simplifie en

[ P₀ ==> B>=0 ] en s

On choisit donc de prendre P₀ := B>=0 comme précondition.

Exercice 3

Construction de l'automate : A1 (.pdf , .html)

Deux étapes :

Élimination des epsilon-transitions : A1 sans espilon (.pdf , .html)

Déterminsation : A2 = Determinisation de A1 sans epsilon (.pdf , .html)

Renomage : A2r = Renaming 1={1} 2={1,2,4,5} 3={1,3} 4={1,4,5} 5={3} (.pdf , .html)

Minimisation: A3 = Minimization de A2r (.pdf , .html)

Minimisation:

initial partition = { {1,2,3,4,5} }

states 1 ≈/≈ 5 : NOT same accepting status So, {1,2,3,4,5} is splitted into {1,2,3,4} U {5}

states 1 ≈/≈ 2 : NOT same behavior on symbol 'b' So, {1,2,3,4} is splitted into {1,3} U {2,4}

states 2 ≈/≈ 4 : NOT same behavior on symbol 'c' So, {2,4} is splitted into {2} U {4}

final partition = { {1,3} , {2} , {4} , {5} }

Footnotes:

B*c + p = B²

c>=0

B * (c-1) + p+B = B²

⁴

c>=1