Algorithme CYK

Algorithme de Cocke-Younger-Kasami

L'algorithme de Cocke-Younger-Kasami permet de déterminer si une phrase peut être générée par une grammaire non contextuelle, et si oui, de quelle manière. L'algorithme permet d'obtenir l'arbre syntaxique de la phrase. Si la grammaire est pondérée, CYK permet de générer l'arbre le plus lourd qui engendre la phrase. Le temps de calcul de cet algorithme est de l'ordre de n³.

Voir aussi

  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Algorithme de Cocke-Younger-Kasami ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme CYK de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • CYK (Algorithme) — Algorithme de Cocke Younger Kasami L algorithme de Cocke Younger Kasami permet de déterminer si une phrase peut être générée par une grammaire non contextuelle, et si oui, de quelle manière. L algorithme permet d obtenir l arbre syntaxique de la… …   Wikipédia en Français

  • CYK (algorithme) — Algorithme de Cocke Younger Kasami L algorithme de Cocke Younger Kasami permet de déterminer si une phrase peut être générée par une grammaire non contextuelle, et si oui, de quelle manière. L algorithme permet d obtenir l arbre syntaxique de la… …   Wikipédia en Français

  • Cyk (algorithme) — Algorithme de Cocke Younger Kasami L algorithme de Cocke Younger Kasami permet de déterminer si une phrase peut être générée par une grammaire non contextuelle, et si oui, de quelle manière. L algorithme permet d obtenir l arbre syntaxique de la… …   Wikipédia en Français

  • CYK — Algorithme de Cocke Younger Kasami L algorithme de Cocke Younger Kasami permet de déterminer si une phrase peut être générée par une grammaire non contextuelle, et si oui, de quelle manière. L algorithme permet d obtenir l arbre syntaxique de la… …   Wikipédia en Français

  • Cyk — Algorithme de Cocke Younger Kasami L algorithme de Cocke Younger Kasami permet de déterminer si une phrase peut être générée par une grammaire non contextuelle, et si oui, de quelle manière. L algorithme permet d obtenir l arbre syntaxique de la… …   Wikipédia en Français

  • Algorithme de Cocke-Younger-Kasami — L algorithme de Cocke Younger Kasami (CYK) est un algorithme d analyse syntaxique pour les grammaire non contextuelle. Il permet de déterminer si un mot peut être engendré par une grammaire, et si oui, d en donner une dérivation. L algorithme… …   Wikipédia en Français

  • Langage algébrique — En théorie des langages formels, un langage algébrique ou langage non contextuel est un langage qui peut être engendré par une grammaire algébrique. De manière équivalente un langage algébrique est un langage reconnu par automate à pile. Les… …   Wikipédia en Français

  • Grammaire non contextuelle — En linguistique et en informatique, une grammaire non contextuelle, grammaire hors contexte ou grammaire algébrique (type 2 dans la hiérarchie de Chomsky) est une grammaire formelle dans laquelle chaque règle de production (ou simplement… …   Wikipédia en Français

  • Forme normale de Chomsky — En informatique théorique, et notamment en théorie des langages, une grammaire algébrique est en forme normale de Chomsky si et seulement si toutes ses règles de production sont de la forme : ou ou où X,Y,Z sont des symboles non terminaux, a …   Wikipédia en Français

  • CKY — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom.   Sigles d’une seule lettre   Sigles de deux lettres > Sigles de trois lettres   Sigles de quatre lettres …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”