Question 1.1 : Pouvez-vous expliquer la définition d'un langage rationnel sans utiliser les notations mathématiques ?
Réponse
Bon, avant de commencer, sachez que je ne pourrai pas être plus précis qu'en utilisant les outils mathématiques. Il est nécessaire à ce niveau d'étude d'être capable de comprendre des descriptions un peu formelles. Il est important de faire l'effort e comprendre ces notations. Ceci dit, la définition d'un langage rationnel (ou régulier) est assez simple (Chapitre 3, section 2). C'est une définition par "construction". On considère les cas de base. Ce sont des axiomes. Ils sont rationnels "par définition". On trouve le langage vide, le langage ne contenant que le mot vide et tous les langages ne contenant qu'un seul mot d'un seul symbole de l'alphabet. Puis, on considère des opérateurs et on dit : tout langage construit par l'application de ces opérateurs sur des langages rationnels sont rationnels. Par exemple, tout langage construit par concaténation de mots pris dans deux langages rationnels est rationnel. Du coup, cette définition permet de montrer qu'un langage est rationnel si l'on arrive à montrer qu'en prenant des langages de base et en les combinant avec les trois opérateurs "autorisés" on retrouve ce langage. Attention, c'est la théorie, car trouver cette décomposition peut s'avérer extrêmement complexe. On utilisera alors d'autres théorèmes pour arriver à nos fins.
Question 1.2 : Cette définition pose un problème. Si on qualifie un langage de "rationnel", on admet qu'il existe des langages non rationnels. Or cette définition ne permet pas de distinguer un langage rationnel d'un autre.
Réponse : Oui, il y a des langages non-rationnels. Si cette définition permet de les distinguer. Tous les langages ne peuvent pas être définis par ces règles. Donc, si vous pouvez décrire le langage UNIQUEMENT avec les langages de base et les trois opérateurs, il est rationnel.
Question 1.3 : D'après la définition, on pourrait conclure que tous les langages sont rationnels puisqu'ils sont une combinaison des cas de base.
Réponse : non
Question 1.4 : Pouvez-vous me donner des exemples de langages non rationnels ?
Réponse : L'exemple classique : a^nb^n (des "a" puis des "b" mais en même nombre) ou les mots palindromes... Là, vous ne pouvez pas décrire ce langage en utilisant uniquement les cas de base et les opérateurs. Intuitivement (ce n'est pas toujours le cas), dès qu'il faut "compter" ou "mémoriser", le langage n'est pas rationnel. Attention ! cette "règle" n'en est pas une, car, par exemple, on peut contrôler la parité. Vous verrez dans la suite du cours des moyens de montrer qu'un langage est rationnel (par exemple en construisant un automate) ou n'est pas rationnel (lemme de l'étoile).
Question 1.5 : Dans le troisième chapitre, la solution proposée du 3ème exercice de la partie concernant les expressions régulières est : l'expression rationnelle permettant de décrire : l'ensemble des mots sur {a,b,c} tels que toute paire de "a" est immédiatement suivie d'une paire de "b" est (ab|ac|b|c|aabb)*a?. "a" appartient bien au langage L généré par cette expression (la mise à l'étoile de (ab|ac|b|c|aabb) peut donner epsilon et a? donne a), de même "ab" appartient bien à L par cette expression (choix parmi (ab|ac|b|c|aabb)* et a? peut être epsilon)
si "a" et "ab" sont concaténés, on obtient le mot "aab". Est ce que "aab" appartient à L ? Si oui, on a donc 2 "a" qui ne sont pas suivi immédiatement de 2 "b".
Réponse : Attention, vous confondez le langage L et le langage LxL. Si "a" et "ab" appartiennent à L alors "a"."ab" appartient à LxL mais pas à L.
Question 1.6 : En général, si deux mots u, v et w appartient à un langage L, est ce que uvw, vuw, wvu, ... appartient également à ce langage L ?
Réponse : non, pas nécessairement (mais ça peut arriver, par exemple avec L*).
Question 1.7 : Chapitre 3 "langages formels" du module. Dans l'exercice 4.1 , il est demandé les définitions rationnelles permettant de décrire le langage dont les mots sont les nombres décimaux. La réponse donnée est la suivante :
Est-il possible de décrire la partie décimale de la manière suivante :PartieDecimale -> [0-9]*[1-9] | 0 | [1-9] ?
En effet, si l'on prend [1-9][0-9]* (dans la réponse donnée dans le cours), on peut obtenir des nombres du type 0,400. Cela est évité en écrivant [0-9]*[1-9] à la place. On ajouter le 0 pour pouvoir inclure 0,0 dans le langage exprimé, et [1-9] pour les nombres avec une seule décimale.
Réponse : Oui, évidemment, votre solution de la partie décimale est la bonne. Par contre [1-9] est contenu dans [0-9]*[1-9] (* signifie 0 ou plusieurs...) donc quand c'est 0 il reste [1-9]. Cette petite "coquille" a été corrigée depuis la version 2.7 ! Cependant, je laisse la remarque qui, à mon avis, reste intéressante.
Question 1.8 : Je n'ai compris le paragraphe sur les systèmes d'équations rationnelles et particulièrement, comment résolvez-vous :
X=a1X+a2Y+a3
Y=b1X+b2Y+b3
avec ai, bi (i=1,2,3) des expressions rationnelles.
Alors une solution est :
X=(a1|a2b2*b1)*(a3|a2b2*b3)
Y=(b2|b1a1*a2)(b3|b1a1*a3)
Réponse :
X=a1X + a2Y + a3
Y=b1X + b2Y + b3
Y = b2*(b1X + b3)
X = a1X + a2b2*(b1X + b3) = a1X + a2b2*b1X + a2b2*b3 + a3
= (a1 + a2b2*b1)X + a2b2*b3 + a3
= (a1 + a2b2*b1)*(a2b2*b3 + a3)
Ce qui fait en er : X = (a1|a2b2*b1)*(a3|a2b2*b3) ce qui est la solution avancée. On fait la même chose pour Y !
Question 2.1 : Pouvez-vous me donner un exemple d'axiome S d'une grammaire ? je ne vois pas très bien ce qu'est S.
Réponse :
L'axiome permet soit d'entamer la génération (c'est l'amorce du traitement) soit de conclure (l'analyse est terminée quand tout est réduit à S
Par exemple, si on a la grammaire G={ {a,b}, {S}, S, R} avec R : S -> aS | b
Alors, pour la génération, on prend S et on applique les règles possibles jusqu'? ne plus avoir que des symboles terminaux :
S -> aS -> aaS -> aab
S -> b
S -> aS -> ab
etc.
Pour la vérification, on fait en sens inverse. Pas exemple, est-ce que aaaab appartient au langage décrit par G ?
aaaab -> aaaaS -> aaaS -> aaS -> aS -> S
On termine car on obtient S. On en conclu que le mot est bien dans le langage.
Question 2.2 : Quand on a une règle du style "S -> aSbSa | c", comment et dans quel ordre doit-on choisir la dérivation à appliquer dans l'arbre ? Si on choisit "aSbSa", on a une récursion infinie alors que si on choisit c on termine.
Réponse :
En fait, il n'y a pas à choisir ! Si vous cherchez à valider un mot, il faut explorer toutes les solutions possibles jusqu'à trouver un arbre correct. En cas de génération de mots, là encore, il faut prendre toutes les solutions. Sur votre exemple, cela veut simplement dire que le langage est infini. vous pourrez générer :
- c
- acbca
- aacbcabca...
Question 2.3 : Pour la classification des grammaires, c'est assez abstrait et je ne vois pas ce que veux dire que telle grammaire est contextuelle, telle autre hors-contexte, je trouve qu'elles sont toutes pareilles : quel est le but de les classifier ?
Réponse : Leur nom est associé à une définition spécifique. Appuyez-vous sur les exercices pour mieux comprendre.
Question 2.4 : Grammaire de Chomski. Comment on voit qu'une grammaire appartient à un type particulier ?
Réponse : Les grammaires ont des contraintes croissantes. Autrement dit, une grammaire régulière est une grammaire hors-contexte mais avec de nouvelles contraintes. Aussi, si on dit qu'une grammaire est régulière alors elle est aussi "hors-contexte". Donc, donner le type d'une grammaire c'est indiquer le type le plus contraint possible. Par déduction, elle sera aussi des types moins contraints. Il faut donc prendre chaque règle de la grammaire et vérifier si elle correspond à la définition de la classe. On commencera par la classe la plus élevée (type le plus contraint). Si toutes les règles sont Ok, la grammaire est du ce type, sinon on recommence la vérification avec le type juste en dessous. Exemple: On va tout d'abord vérifier que c'est une grammaire de type linéaire (droit ou gauche), si ce n'est pas le cas, on continue la vérification avec la grammaire hors contexte, et ainsi de suite jusqu'à ce qu'on trouve le bon type.
Question 3.1 : Pourriez-vous, m'expliquer comment fonctionne le lemme de l'étoile car je ne comprend pas trop comment ?a marche ?
Réponse :
Le lemme de l'étoile est probablement une des parties les plus difficiles de ce cours. Le fond du lemme est assez simple. Les automates d'état fini ont (par définition) un nombre fini d'états. Les langages rationnels sont des langages reconnaissables par des AFN. Donc, qui dit langage rationnel dit AFN. Maintenant, quel est le plus long mot reconnu par un automate en passant qu'une seule fois par un état ? Si n est le nombre d'état alors le mot aura une longueur inférieure ou égale à n-1. L'automate est alors linéaire. Si un mot est reconnu et possède une longueur m supérieure à n. L'automate ayant toujours n états alors lors de la reconnaissance de ce dernier mot, l'automate est passé au moins deux fois par un même état. S'il est passé deux fois alors il existe des mots qui vont permettre de passer plusieurs par cet état. Nous avons mis en évidence un facteur itérant. Et bien, le lemme de l'étoile c'est la mise en évidence de ce facteur itérant. C'est le v qui peut, mis à l'étoile, donner un ensemble de mots qui seront aussi dans le langage. Donc le lemme de l'étoile nous dit : Il existe un N (le nombre d'états de l'automate par exemple mais ce n'est as nécessaire de le connaitre car n+1000 marche aussi !), tel que tout mot z de longueur supérieure à ce N peut se décomposé en uvw. v est un facteur itérant candidat. donc, sous r?serve des conditions du lemme, uv^iw doit aussi être dans le langage (on peut faire autant de tours que l'on veut).