Comprendre les grammaires algébriques linéaires (dites aussi régulières)

[@youssoufcherifmahamatnour9015]

Vos vidéos sont très bien expliquées. Merci pour ces détails

[@informatiquetheorique9146]

Merci

[@accounttutos9502]

Bonjour je viens decouvrir ta chaine et tes tutos c'est vraiment tres fort ce que tu fais !

[@informatiquetheorique9146]

Merci beaucoup 😁

[@hindelmouden4392]

Vraiment merci beaucoup.

[@fizzisop4175]

Bonjour, tout d'abord merci pour cette video claire et rapide. Je n'arrive pas à produire un automate lorsqu'on commence à partir de règles d'une grammaire algébrique linéaire gauche, quelle astuce faut-il utiliser à ce moment là ?

[@informatiquetheorique9146]

Bonjour, Une possibilité est "d'inverser les règles". C'est-à-dire que l'on construit une nouvelle grammaire : s'il y a avait par exemple une règle S - > Tabbc dans la première grammaire, on obtient la règle S -> cbbaT F -> epsilon rest F - > epsilon S -> baa devient S -> aab On écrit les parties droite dans l'autre sens. On obtient une grammaire linéaire droite si la grammaire initiale est linéaire gauche. On peut appliquer à cette grammaire l'algorithme de la vidéo. Le truc c'est que la nouvelle grammaire reconnaît le langage miroir de la la grammaire initiale. Et là il y a une construction très simple pour obtenir un automate pour le langage initial. Il est possible de faire directement la construction. Voilà deux liens kzbin.info/www/bejne/bnSYf5qOd5d9qqc kzbin.info/www/bejne/jZKyg2hqnqZqraM pour la définition du miroir et pour la construction (très simple) sur les automates.

[@fizzisop4175]

@@informatiquetheorique9146 Merci beaucoup je vais checker tout ça

[@aminerhouma8778]

merci

[@informatiquetheorique9146]

😀

[@accounttutos9502]

stp j'ai besoin de ton aide sur certaines question : 1)Comment montrez que l'ensemble des langages algebriques est clos par l'union ? 2) Soit G = (N,T,P,S ) une grammaire algebrique 2 1) peut on construire un AFN A qui accepte le meme langage que celui denote par G ? Si justifiez votre reponse ? 2 2) peut on construire un AFD A qui accepte le meme langage que celui denote par G ? Si justifiez votre reponse ? 2 3) Peut on construire un analyseur par descente recursive pour le langage L( G ) ? justifier votre reponse

[@informatiquetheorique9146]

Je pense que les réponse sont dans le cours de l'enseignant(e). Pour 1), il suffit de renommer les symbole non terminaux de la seconde grammaire, puis de prendre l'union des productions des deux grammaires, plus la règle S->S1|S2 où S1 est l'axiome de la première grammaire et S2 celui de la seconde. 2) et 3) me semblent la même question vu que les automates déterministes et non déterministe reconnaissent les même langages. La réponse est "en général non", car certains langages algébriques ne sont pas régulier, par exemple {a^nb^n | n >=0}. Si les question portent sur des automates à pile, c'est faux pour 2) et vrai pour 3). 4) Uniquement si la grammaire est LL1 me semble-t-il mais je n'ai pas fais d'analyse syntaxique depuis un moment et c'est un peu technique, je me trompe peut-etre.

[@accounttutos9502]

@@informatiquetheorique9146 merci vraiment avez vous des pdf exo sur les automates et gramaires pour s'exercer svp Mr?

[@informatiquetheorique9146]

@@accounttutos9502 Non, rien de propre. Mais on peut en trouver plein sur le net.