» 
allemand anglais arabe bulgare chinois coréen croate danois espagnol estonien finnois français grec hébreu hindi hongrois islandais indonésien italien japonais letton lituanien malgache néerlandais norvégien persan polonais portugais roumain russe serbe slovaque slovène suédois tchèque thai turc vietnamien
allemand anglais arabe bulgare chinois coréen croate danois espagnol estonien finnois français grec hébreu hindi hongrois islandais indonésien italien japonais letton lituanien malgache néerlandais norvégien persan polonais portugais roumain russe serbe slovaque slovène suédois tchèque thai turc vietnamien

définition - Hiérarchie de Chomsky

voir la définition de Wikipedia

   Publicité ▼

dictionnaire collaboratif

Vous pouvez participer à l'enrichissement du dictionnaire et proposer vos propes définitions pour ce mot ou un autre.

Inscription possible avec votre compte Facebook

Wikipedia

Hiérarchie de Chomsky

                   
  Hiérarchie de Chomsky, avec classes de langages et classes d'automates associés

En informatique théorique, en théorie des langages, et en calculabilité, la hiérarchie de Chomsky est une classification des langages formels et des grammaires formelles, décrite par Noam Chomsky en 1956[1].

Les classes de langages L0, L1, L2, L3 (chaque langage étant un ensemble de mots) de la hiérarchie sont strictement imbriquées : L3 \subset L2 \subset  L1 \subset  L0 \subset U. Ici U est l'univers de tous les langages.

Sommaire

  Définition

Une grammaire formelle est constituée de quatre objets :

  • T : ensemble fini de symboles terminaux, appelé alphabet terminal;
  • N : ensemble fini de symboles non terminaux ou alphabet des variables;
  • R : ensemble fini de règles;
  • S (S\in N) : axiome (symbole de départ).

Les alphabets T et N sont disjoints. L'alphabet terminal est parfois noté \Sigma ou A. Dans la suite, on note V=T\cup N.

Une règle est un couple (x,y) de mots sur V, avec la condition que x contient au moins une variable. On écrit souvent x\to y au lieu de (x,y).

Une dérivation immédiate du mot u en le mot v consiste à remplacer, dans u, une occurrence de x par y; en d'autres termes, u dérive immédiatement en v par l'emploi de la règle (x,y) si u=pxs et v=pys pour des mots p et s. Une dérivation est une suite de dérivations immédiates consécutives. En d'autres termes, la dérivation est la fermeture réflexive et transitive de la relation de dérivation immédiate.

Le langage engendré par une grammaire est l'ensemble des mots sur l'alphabet terminal, donc ne contenant plus de variables, qui l'on peut dériver à partir de l'axiome S.

Les règles d'une grammaire définissent les lois d’enchâssement des mots du langage. Les langues naturelles ont une grammaire bien plus complexe que celle des langages de programmation ; il n’est pas possible de la formaliser entièrement de cette façon.

  Quatre classes de grammaires et de langages

Chomsky a défini quatre classes de grammaires, nommées de type 0 à type 3, et donc aussi quatre classes de langages, engendrés par ces grammaires hiérarchiquement imbriquées. Les langages de type 0 sont les plus généraux: ce sont les langages récursivement énumérables. Ils contiennent les langages de type 1, les langages contextuels, en anglais « context-sensitive ». Les langages de type 2 sont appelés langage algébriques) ou « hors contexte », en anglais « context-free ». Ils contiennent eux-mêmes les langages de type 3, les langages « réguliers » ou langages rationnels. Parfois, on ajoute une dernière classe, composée des langages finis.

  Type 0 : grammaires générales

Aucune restriction n'est imposée aux règles. Elles ont la forme :

\alpha \rightarrow \beta\quad\quad(\alpha \in V^*NV^*, \beta \in V^*)

Ces grammaires génèrent la classe des langages récursivement énumérables. Ce sont exactement les langages reconnaissables par machine de Turing. Le problème de l'appartenance d'un mot à un langage de cette classe est indécidable.

  Type 1 : grammaires contextuelles

Article détaillé : Grammaire contextuelle.

Les règles sont de la forme :

\alpha A\beta \rightarrow \alpha\gamma\beta\qquad(A \in N, \alpha,\beta,\gamma \in V^*,\gamma \neq \varepsilon)

Autrement dit, toute règle comprend un non-terminal entouré de deux mots qui décrivent le contexte dans lequel la variable peut être remplacée. Ces grammaires sont dites contextuelles (en anglais context-sensitive), car le remplacement d'un élément non-terminal peut dépendre des éléments autour de lui : son contexte. Les langages produits, appelés langages contextuels ou sensibles au contexte, sont exactement ceux reconnus par une machine de Turing non déterministe à mémoire linéairement bornée, appelés couramment automates linéairement bornés. D'autres formulations équivalentes existent pour les grammaires définissant les langages contextuels.

  Type 2 : grammaires non contextuelles ou algébriques

Article détaillé : Grammaire non contextuelle.

Les règles sont de la forme :

A \rightarrow \gamma\qquad(A \in N, \gamma \in V^*)

Ce sont des grammaires contextuelles où le contexte est vide, ce qui signifie que les symboles non terminaux sont traités indépendamment de la place où ils apparaissent. Ces grammaires engendrent exactement les langages algébriques, appelés aussi langages hors contexte, langages acontextuels, ou langages non contextuels. Ils sont reconnus par un automate à pile.

  Type 3 : grammaires régulières

Article détaillé : Grammaire régulière.

Les grammaires régulières sont soit les grammaires linéaires gauches ou les grammaires linéaires droites :

  • Dans les grammaires linéaires gauches, les règles sont de la forme :
A \rightarrow Ba,\quad A \rightarrow a\qquad(A,B \in N, a \in T)
  • Dans les grammaires linéaires droites, les règles sont de la forme :
A \rightarrow aB,\quad A \rightarrow a\qquad(A,B \in N, a \in T)

Les grammaires régulières engendrent les langages rationnels. En effet, une grammaire régulière se transforme facilement en un automate fini (théorème de Kleene).

On ne peut pas autoriser les deux types de règles simultanément dans une grammaire sans sortir la classe des langages rationnels : on obtient les grammaires linéaires qui constituent une classe intermédiaire entre le type 2 et le type 3. Les règles d'une grammaire linéaire sont de la forme :

A \rightarrow aBb,\quad A \rightarrow a\qquad(A,B \in N, a,b \in T\cup\varepsilon)

  Récapitulation

Grammaire Langage Automate Règles de production
Type-0 récursivement énumérable Machine de Turing \alpha \rightarrow \beta
Type-1 contextuel Automate linéairement borné \alpha A\beta\rightarrow\alpha\gamma\beta
Type-2 algébrique Automate à pile non déterministe A \rightarrow \gamma
Type-3 rationnel Automate fini A \rightarrow aB,\quad A \rightarrow a

  Exemples

  • Langages réguliers :
    a^*b^*,\quad (aaab)^*,\quad \{a^{3i} : i>0\}.
  • Langages algébriques qui ne sont pas rationnels :
    \{a^i b^i : i>0\}\,, l'ensemble des palindromes (qui est même un langage linéaire, comme le précédent), le langage de Dyck
  • Langages contextuels qui ne sont pas algébriques :
    \{a^i b^i c^i : i>0\},\quad \{a^i b^k c^i d^k : i>0, k>0\},\quad \{uu : u\in\{a,b\}^*\}.

Voir aussi les exemples sur la page grammaire formelle. La théorie des langages formels dispose de nombreux outils pour affirmer, ou infirmer, le type d'un langage (rationnel, algébrique etc.). La construction explicite d'une grammaire reconnaissant un langage donné n'est pas toujours facile.

  Raffinement de la hiérarchie de Chomsky

La hiérarchie originale de Chomsky comprenait quatre classes. On peut facilement en ajouter d'autres[2],[3],[4]:

  • entre le type 0 et le type 1, les langages récursifs, qui sont acceptés par les machines de Turing qui s'arrêtent toujours,
  • entre le type 1 et le type 2, les langages à grammaires indexées (en), définis par des grammaires plus générales que les grammaires contextuelles,
  • entre le type 2 et le type 3, les langages algébriques déterministes, pour lesquels il existe une caractérisation par automate, mais pas par les grammaires[5].

Les grammaires d'arbres adjoints[6],[7] définissent une famille entre les langages algébriques et les langages contextuels. Ils sont acceptés par les automates à à pile embarquéee (en)[8]. Ces grammaires font partie des grammaires qui permettent de mieux cerner la structure des langues naturelles, regroupés sous le nom langage légèrement sensible au contexte (en)[9].

D'autres raffinements existent, qui montrent que la structure n'est pas « linéaire »: par exemple, si l'on compare les langages linéaires et les langages algébriques déterministes, on s’aperçoit que ces familles ne sont pas contenues l'une dans l'autre.

  Extension de cette hiérarchie

La hiérarchie de Chomsky concerne uniquement le domaine du calculable défini paradigmalement par ce que peut calculer une machine de Turing. Au delà existent d'autres hiérarchies de langages dont la hiérarchie arithmétique.

  Bibliographie

  • Noam Chomsky,
    • 1959a On certain formal properties of grammars, Information and Control 2: 137–67.
    • 1959b A note on phrase structure grammars, Information and Control 2: 393–95.
    • 1962 Context-free grammars and and pushdown storage, RLE Quart.Prog. Rept. No. 65. Cambridge, Mass.: MIT.
  • John E. Hopcroft et Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979 
  • Daniel I. A. Cohen, Introduction to Computer Theory, John Wiley & Sons, 1997 
  • Peter Linz, An introduction to Formal Languages and Automata, Jones and Bartlett, 2001, 3e éd. (ISBN 978-0763714222) 

  Notes et références

  1. Noam Chomsky, « Three models for the description of language », dans IRE Transactions on Information Theory, no 2, 1956, p. 113–124 [texte intégral] 
  2. Cohen, 1997, Chap. 30 : The Chomsky Hierarchy
  3. Hopcroft, Ullman 1979, Chap. 9: The Chomsky Hierarchy. La réédition de cet ouvrage en 2001 avec Rajeev Motwani (en) ne comporte plus ce chapitre.
  4. Linz, 2001, Chap. 11.4 : The Chomsky Hierarchy.
  5. Hopcroft, Ullman 1979, Chap. 10 : Deterministic context-free languages.
  6. A.K. Joshi, L.S. Levy, et M. Takahashi, « Tree adjunct grammars », Journal of Computer Systems Science, 10(1), 1975.
  7. Unification-Based Tree Adjoining Grammars
  8. K. Vijay-Shanker, « A Study of Tree-Adjoining Grammars », dans Ph.D. Thesis, University of Pennsylvania, janvier 1988 
  9. voir aussi: Robert McNaughton, «An insertion into the Chomsky hierarchy?», Jewels are forever, 1999, pages 204-212, et T. Jurdziński, K. Lorys, G. Niemann, F. Otto, «Some results on RWW- and RRWW-automata and their relation to the class of growing context-sensitive languages», Journal of Automata, Languages and Combinatorics, Volume 9 Numéro 4, Octobre 2004

  Articles connexes

   
               

 

Toutes les traductions de Hiérarchie de Chomsky


Contenu de sensagent

  • définitions
  • synonymes
  • antonymes
  • encyclopédie

Dictionnaire et traducteur pour mobile

⇨ Nouveau : sensagent est maintenant disponible sur votre mobile

   Publicité ▼

sensagent's office

Raccourcis et gadgets. Gratuit.

* Raccourci Windows : sensagent.

* Widget Vista : sensagent.

dictionnaire et traducteur pour sites web

Alexandria

Une fenêtre (pop-into) d'information (contenu principal de Sensagent) est invoquée un double-clic sur n'importe quel mot de votre page web. LA fenêtre fournit des explications et des traductions contextuelles, c'est-à-dire sans obliger votre visiteur à quitter votre page web !

Essayer ici, télécharger le code;

SensagentBox

Avec la boîte de recherches Sensagent, les visiteurs de votre site peuvent également accéder à une information de référence pertinente parmi plus de 5 millions de pages web indexées sur Sensagent.com. Vous pouvez Choisir la taille qui convient le mieux à votre site et adapter la charte graphique.

Solution commerce électronique

Augmenter le contenu de votre site

Ajouter de nouveaux contenus Add à votre site depuis Sensagent par XML.

Parcourir les produits et les annonces

Obtenir des informations en XML pour filtrer le meilleur contenu.

Indexer des images et définir des méta-données

Fixer la signification de chaque méta-donnée (multilingue).


Renseignements suite à un email de description de votre projet.

Jeux de lettres

Les jeux de lettre français sont :
○   Anagrammes
○   jokers, mots-croisés
○   Lettris
○   Boggle.

Lettris

Lettris est un jeu de lettres gravitationnelles proche de Tetris. Chaque lettre qui apparaît descend ; il faut placer les lettres de telle manière que des mots se forment (gauche, droit, haut et bas) et que de la place soit libérée.

boggle

Il s'agit en 3 minutes de trouver le plus grand nombre de mots possibles de trois lettres et plus dans une grille de 16 lettres. Il est aussi possible de jouer avec la grille de 25 cases. Les lettres doivent être adjacentes et les mots les plus longs sont les meilleurs. Participer au concours et enregistrer votre nom dans la liste de meilleurs joueurs ! Jouer

Dictionnaire de la langue française
Principales Références

La plupart des définitions du français sont proposées par SenseGates et comportent un approfondissement avec Littré et plusieurs auteurs techniques spécialisés.
Le dictionnaire des synonymes est surtout dérivé du dictionnaire intégral (TID).
L'encyclopédie française bénéficie de la licence Wikipedia (GNU).

Copyright

Les jeux de lettres anagramme, mot-croisé, joker, Lettris et Boggle sont proposés par Memodata.
Le service web Alexandria est motorisé par Memodata pour faciliter les recherches sur Ebay.
La SensagentBox est offerte par sensAgent.

Traduction

Changer la langue cible pour obtenir des traductions.
Astuce: parcourir les champs sémantiques du dictionnaire analogique en plusieurs langues pour mieux apprendre avec sensagent.

Dernières recherches dans le dictionnaire :

2743 visiteurs en ligne

calculé en 0,047s

   Publicité ▼

Je voudrais signaler :
section :
une faute d'orthographe ou de grammaire
un contenu abusif (raciste, pornographique, diffamatoire)
une violation de copyright
une erreur
un manque
autre
merci de préciser :

Mon compte

connexion

inscription

   Publicité ▼