IFT-2002 Informatique Théorique Devoir 1 À remettre le 12 octobre avant 17h Que

IFT-2002 Informatique Théorique Devoir 1 À remettre le 12 octobre avant 17h Question 1. Construisez des automates finis qui acceptent les langages suivants. Les automates peuvent être non-déterministes si cela vous simplifie la tâche. Par contre, vous ne pouvez pas utiliser des transitions étiquetées par un mot (voir p. 38 des notes de cours) ou par une expression régulière. • L’ensemble des mots sur l’alphabet {0, 1} où tous les 0 (s’il y en a) apparaissent par groupe de trois. Notons que des groupes successifs de 0 sont possibles (c’est à dire des blocs de 0 de longueur 6, 9, 12, etc.) Ainsi 110001110000001 est un mot qui appartient au langage parce qu’il contient un bloc de trois 0 et ensuite deux blocs consécutifs de trois 0. Par contre 10011000 et 10001100000 ne font pas partie du langage. • L = {a1a2 . . . an : n ∈N+ ∧ai ∈{a, b} ∧((i pair) →ai = b)}. En d’autres mots, L contient les mots non-vides où toutes les lettres en position paire sont des b. Question 2. Donnez des expressions régulières qui représentent les deux langages de la question 1. Question 3. Construisez un automate déterministe qui accepte le même langage que l’automate non-déterministe ci-dessous. Question 4. Pour les deux questions suivantes, on fixe l’alphabet à {a, b}. Pour un mot w ∈{a, b}∗on définit ˆ w (appelons ˆ w le négatif de w) comme étant le mot obtenu à partir de w en remplaçant les a par des b et les b par des a. Voici une liste d’exemples: si w = aba alors ˆ w = bab si w = aa alors ˆ w = bb si w = bbba alors ˆ w = aaab si w = λ alors ˆ w = λ Montrez que le langage suivant n’est pas régulier. K = {w ˆ w : w ∈{a, b}∗}. (En d’autres mots, K est l’ensemble des mots qui peuvent être coupés en deux moitiés ou la seconde est le négatif de la première. Par exemple, ababab, aabb et bbbaaaab font partie de K mais babb, aaba et aba ne font pas partie de K.) 1 Question 5. Soit L ⊆{a, b}∗. Par extension de la définition de la question précédente, on pose ˆ L = { ˆ w : w ∈L}. Par exemple, si L = {ab, bab, bbb} alors ˆ L = {ba, aba, aaa}. Montrez que si L est un langage régulier alors ˆ L est aussi un langage régulier. (Il y a deux façons principales de procéder. La première est de montrer comment on peut partir d’un automate M qui accepte L et le modifier pour obtenir un automate M ′ qui accepte ˆ L. La seconde est de montrer comment on peut partir d’une expression régulière r qui représente L et la modifier pour obtenir une expression régulière r′ qui représente ˆ L.) Question 6. Soit Σ l’alphabet de 8 symboles  0 0 0  ,  0 0 1  ,  0 1 0  , . . . ,  1 1 1  . Un mot w ∈Σ∗de longueur n peut-être vu à la fois comme une suite de n colonnes de 3 bits ou comme 3 rangées de n bits qui peuvent être interprétées comme 3 entiers aw, bw, cw écrits en représentation binaire. Montrez que le langage L ⊆Σ∗des w tels que aw + bw = cw est un langage régulier. Par exemple, on aura  0 0 1  1 1 0  0 1 1  ∈L puisque dans ce cas on a aw = 2, bw = 3 et cw = 5. Note: il est à mon avis plus facile de montrer que Lr est régulier et de faire ensuite appel au théorème vu en classe. Question 7. Donnez une expression régulière qui représente le langage accepté par l’automate ci-dessous. Donnez les étapes intermédiaires (c’est pour votre bien et celui de mon correcteur). 1" 2" 3" a" a" b" b" 0" b" a" Question 8. (facultative) Soit L, K ⊆{a, b}∗deux langages réguliers. Montrez que le langage suivant est également régulier. H = {c1d1c2d2 . . . cndn : n ∈N ∧ci, di ∈{a, b} ∧c1 . . . cn ∈L ∧d1 . . . dn ∈K}. En d’autres termes, H contient les mots w de longueur paire qui ont la propriété suivante: le mot formé par les lettres en position impaire appartient à L et celui formé par les lettres en position paire appartient à K.(Les bonnes idées qui ne marchent pas tout à fait seront récompensées!) 2 uploads/s3/ devoir-informatique-theorique.pdf

Tags
Administrationquestion langage alors expression comme
Documents similaires
  • 33
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager