Discuter:Hiérarchie de Chomsky

Un article de Wikipédia, l'encyclopédie libre.

	Hiérarchie de Chomsky fait partie du projet Langues, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés à la linguistique et aux langues. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet, où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs.
Bon début	Cet article a été classé comme d'Avancement BD selon le Tableau d'évaluation du projet. (Voir les statistiques)
Moyenne	Cet article a été classé comme d'Importance moyenne selon le Tableau d'évaluation du projet. (Contester?)

Cet article demande à être élaboré. Il est très peu expliqué et est un peu redondant avec Grammaire formelle.

--Kozaru (小猿) 28 février 2006 à 22:25 (CET)

Sommaire

1 Exemples
2 À améliorer
3 Grammaires régulières == grammaires linéaires à droite ?
4 Problème de définitions

[modifier] Exemples

Il faudrait en donner pour chaque type de grammaire pour montrer les impacts sur les raisonnements. L'exemple actuel est-il correct ? La "réponse" mériterait quelques explications, sur la question en particulier ! --JeanClem 23 mai 2006 à 11:00 (CEST)

Après avoir relu plusieurs fois ces explications, je reste incapable de jauger un langage pour dire à quelle grammaire il appartient. Je ne nie pas avoir quelques lacunes en mathématiques. Je cherchais à savoir à quel type appartiennent les langages de programmation C et C#. Impossible de faire le lien entre les formules mathématiques abstraites et ces cas concret. Il serait intéressant de donner, pour chaque type, le nom langage connu qui utilise cette grammaire, ou un exemple plus concret que les aaabbbaab+aa qu'on trouve sur tous les sites qui parlent de cette classification. Mose, 8 sept 2006

[modifier] À améliorer

La définition était fausse pour le type 1 ! Il manque des exemples. Pour répondre à la question précédente, si un langage est engendré par une grammaire de type 2 (par exemple), ça veut dire qu'il est de type 2 (donc aussi de type 0 et 1), mais il est peut-être aussi de type 3, si on arrive à trouver une grammaire plus simple pour ce langage. Étant donné un langage, on ne peut pas toujours déterminer son type à coup sûr, par exemple savoir si un langage de type 2 est en fait de type 3 est indécidable. Pour beaucoup de langages de programmation, l'essentiel (du travail) se fait avec le type 2 : pour les expressions arithmétiques, les structures de contrôle (if-then-else, blocs, ...). Mais ils sont le plus souvent de type 1, parce que l'on doit déclarer toutes les variables avant de s'en servir, toutes les fonctions avant ou après qu'on s'en sert, ... Tchai 10 janvier 2007 à 17:26 (CET)

PS. En fait, il y a plus de détails à Grammaire_hors-contexte. Merci à Special:Contributions/194.199.184.126 qui a corrigé le lien. Tchai 26 avril 2007 à 16:39 (CEST)

[modifier] Grammaires régulières == grammaires linéaires à droite ?

Mon prof de théorie des langages (cf son cours) considère que les grammaires régulières se limitent aux grammaires linéaires à droite. C'est aussi ce que j'ai trouvé ici et là. Je suis troublé. Arronax50 18 mars 2007 à 19:17 (CET)

C'est juste une convention. Ce qui est important, c'est de ne pas mélanger les règles de type gauche et droit. Mais les linéaires gauches et les linéaires droites ont exactement le même pouvoir d'expression, et il est facile de les transformer en automate fini... Tchai 20 mars 2007 à 14:56 (CET)

Merci de l'éclaircissement. Arronax50 20 mars 2007 à 18:19 (CET)

[modifier] Problème de définitions

Dans certaines formules, l'article fait référence à $V$ ou $Σ$ sans les définir au préalable. Si j'ai bien compris, $V = N \cup T$ et $Σ = T$ , mais il faudrait soit corriger, soit préciser.