Séance de cours

Transformation de la forme normale de Chomsky

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Dans cours

CS-320: Computer language processing

We teach the fundamental aspects of analyzing and interpreting computer languages, including the techniques to build compilers. You will build a working compiler from an elegant functional language into machine code using a popular backend called LLVM (htt ...

Description

Cette séance de cours couvre la transformation de Chomsky Normal Form (CNF), en commençant par les étapes de conversion d'une grammaire en CNF, telles que l'élimination des symboles improductifs et inaccessibles, l'élimination des productions epsilon et la réduction de l'arité des productions. Il explique également le processus de conversion des terminaux pour se produire seul sur le côté droit et l'élimination des productions unitaires. La séance de cours se termine par l'importance de l'ordre des étapes dans le processus de conversion CNF pour éviter l'explosion exponentielle du nombre de productions.

Enseignant·e

Viktor Kuncak

Viktor Kunčak joined EPFL in 2007, after receiving a PhD degree from MIT. Since then has been leading the Laboratory for Automated Reasoning and Analysis and supervised at least 12 completed PhD theses. His works on languages, algorithms and systems for verification and automated reasoning. He served as an initiator and one of the coordinators of a European network (COST action) in the area of automated reasoning, verification, and synthesis. In 2012 he received a 5-year single-investigator European Research Council (ERC) grant of 1.5M EUR. His invited talks include those at Lambda Days, Scala Days, NFM, LOPSTR, SYNT, ICALP, CSL, RV, VMCAI, and SMT. A paper on test generation he co-authored received an ACM SIGSOFT distinguished paper award at ICSE. A PLDI paper he co-authored was published in the Communications of the ACM as a Research Highlight article. His Google Scholar profile reports an over-approximate H-index of 38. He was an associate editor of ACM Transactions on Programming Languages and Systems (TOPLAS) and served as a co-chair of conferences on Computer-Aided Verification (CAV), Formal Methods in Computer Aided Design (FMCAD), Workshop on Synthesis (SYNT), and Verification, Model Checking, and Abstract Interpretation (VMCAI). At EPFL he teaches courses on functional and parallel programming, compilers, and verification. He has co-taught the MOOC "Parallel Programming" that was visited by over 100'000 learners and completed by thousands of students from all over the world.

Source officielle

Concepts associés (30)

Grammaire générative et transformationnelle

La grammaire générative et transformationnelle est une théorie syntaxique s’inscrivant dans le courant de la linguistique générative. Majoritairement présente en Amérique du Nord, elle s’est développée depuis 1957 sous l’impulsion de Noam Chomsky. Cette théorie tente de caractériser la connaissance de la langue qui permet l'acte effectif du locuteur-auditeur. La grammaire générative est basée sur la distinction entre compétence et performance (connaissance que le locuteur-auditeur a de sa langue contre l’emploi effectif de la langue dans des situations concrètes).

Grammaire non contextuelle

En linguistique et en informatique théorique, une grammaire algébrique, ou grammaire non contextuelle, aussi appelée grammaire hors-contexte ou grammaire « context-free » est une grammaire formelle dans laquelle chaque règle de production est de la forme où est un symbole non terminal et est une chaîne composée de terminaux et/ou de non-terminaux. Le terme « non contextuel » provient du fait qu'un non terminal peut être remplacé par , sans tenir compte du contexte où il apparaît.

Hiérarchie de Chomsky

vignette|Hiérarchie de Chomsky. En informatique théorique, en théorie des langages, et en calculabilité, la hiérarchie de Chomsky (parfois appelée hiérarchie de Chomsky-Schützenberger) est une classification des grammaires formelles (et par extension, des langages formels respectifs engendrés par les grammaires), esquissée par Noam Chomsky en 1956, et décrite de façon formelle en 1959. La hiérarchie introduite par Noam Chomsky repose sur le modèle de grammaire formelle.

Grammaire

La grammaire est l'étude objective et systématique des éléments (phonème, morphème et mot) et des mécanismes et processus de formation, de construction et d'expression constitutifs d'une langue naturelle, écrite ou parlée, en particulier par l'étude de la morphologie et de la syntaxe et à l'exclusion de la phonologie, de la lexicologie, de la sémantique et de la stylistique. Par extension, on nomme aussi grammaire un manuel ou un ensemble de documents décrivant des règles grammaticales.

Relational grammar

In linguistics, relational grammar (RG) is a syntactic theory which argues that primitive grammatical relations provide the ideal means to state syntactic rules in universal terms. Relational grammar began as an alternative to transformational grammar. In relational grammar, constituents that serve as the arguments to predicates are numbered in what is called the grammatical relations (GR) hierarchy. This numbering system corresponds loosely to the notions of subject, direct object and indirect object.

Afficher plus

Séances de cours associées (21)

CYK Algorithme pour l'analyse des grammaires générales

Explore l'analyse des grammaires générales à l'aide de l'algorithme CYK et de Chomsky Normal Form.

CYK Parsing Algorithme pour les grammaires générales

Introduit l'algorithme d'analyse CYK pour les grammaires sans contexte, expliquant sa gestion de l'ambiguïté et de l'importance dans l'analyse des grammaires générales.

Transformation de la forme normale de Chomsky

Couvre la conversion en forme normale de Chomsky en supprimant les symboles improductifs et inaccessibles.

Grammaires et analyseurs: un aperçu du traitement du langage

Fournit une vue d'ensemble des grammaires et des analyseurs dans le traitement du langage informatique.

Grammaires sans contexte: Partie 1

Couvre les grammaires sans contexte, les règles de production, les automates, l'analyse syntaxique et les techniques d'analyse.

Afficher plus

Concepts associés (30)

Grammaire générative et transformationnelle

Grammaire non contextuelle

Hiérarchie de Chomsky

Grammaire

Relational grammar

Afficher plus