Grammaire non contextuelle déterministeEn informatique théorique, et particulièrement dans la théorie des grammaires formelles, les grammaires context-free déterministes ( DCFG ) ou grammaires non contextuelles déterministes sont un sous-ensemble des grammaires non contextuelles. Ce sont les grammaires non contextuelles qui peuvent être dérivées d'automates à pile déterministes, et ils engendrent les langages non contextuels déterministes. Les DCFG sont toujours inambigües et ils constituent une sous-classe importante des grammaires non contextuelles ; il existe cependant des CFG inambigües qui ne sont pas déterministes.
Grammaire ambigüeEn informatique théorique et en théorie des langages, une grammaire ambiguë ou ambigüe est une grammaire algébrique qui admet un mot avec deux dérivations gauches distinctes ou — de manière équivalente — deux arbres de dérivation distincts. L'ambiguïté ou l'inambiguïté est une propriété des grammaires, et non des langages. De nombreux langages admettent à la fois des grammaires ambiguës et inambigües, alors que d'autres ne possèdent que des grammaires ambiguës.
Analyseur LRComme tout analyseur grammatical (ou analyseur syntaxique), un analyseur LR vise à vérifier si une chaîne de caractères (typiquement contenue dans un fichier) possède bien la structure d'une grammaire spécifiée à l'avance. Cette vérification s'accompagne généralement d'actions. Une action typique est la génération d'une autre chaîne de caractères ou encore d'un arbre d'analyse. Ainsi l'analyse grammaticale est généralement utilisée pour la compilation (transformation d'un code source en code machine).
Shift-reduce parserA shift-reduce parser is a class of efficient, table-driven bottom-up parsing methods for computer languages and other notations formally defined by a grammar. The parsing methods most commonly used for parsing programming languages, LR parsing and its variations, are shift-reduce methods. The precedence parsers used before the invention of LR parsing are also shift-reduce methods. All shift-reduce parsers have similar outward effects, in the incremental order in which they build a parse tree or call specific output actions.
Exponential time hypothesisIn computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by . It states that satisfiability of 3-CNF Boolean formulas cannot be solved in subexponential time, i.e., for all constant , where n is the number of variables in the formula. The exponential time hypothesis, if true, would imply that P ≠ NP, but it is a stronger statement.
Langue construitevignette|Le drapeau des langues construites, représentant la tour de Babel. Une langue construite ou planifiée (ou idéolangue, parfois dénommée langue artificielle, ou conlang pour constructed language en anglais) est une langue créée par une ou plusieurs personnes dans un temps relativement bref, contrairement aux langues naturelles dont l'élaboration est en grande partie spontanée et sans plan d'ensemble. Il est donc parfois difficile de cloisonner les langues dans ces deux catégories.
Revitalisation linguistiqueLa revitalisation linguistique est un processus cherchant à empêcher une langue de disparaître et à la faire revivre. Le nombre de s'élève actuellement à quelques dizaines: aïnou, arabe andalou, barngarla, chochenyo, cornique, dalmate, diyari, hawaïen, kaurna, latin, laze, live, léonais, manx, māori, mutsun, gascon, vieux-prussien, palawa kani, sanskrit, wampanoag. Cette liste est ouverte, et des dizaines d'autres langues pourraient y être incluses, tant les efforts de revitalisation linguistique sont répandus dans le monde.
Langue secondeLa notion de langue seconde a deux interprétations principales. L’une provient de la sociolinguistique anglo-saxone, conformément à laquelle une langue seconde est simplement une langue acquise chronologiquement juste après la première, c’est-à-dire après la langue maternelle. Selon une autre interprétation, la notion de langue seconde est englobée dans celle de langue étrangère au sens où c’est une langue autre que la langue maternelle mais se distingue de la langue étrangère par son statut social et, éventuellement, juridique.
Acquisition du langageL'acquisition du langage est un domaine de recherche pluridisciplinaire, relevant notamment de la recherche en psychologie et en sciences du langage, qui vise à décrire et comprendre comment l'enfant acquiert le langage, oral ou gestuel, du milieu qui l'entoure. L'acquisition du langage d'un jeune enfant est rapide et s'effectue sans apprentissage formel. Le langage se développe toute la vie, mais c'est surtout entre la naissance et l'âge de cinq ans, que les apprentissages essentiels sont observés.
Forme normale de GreibachEn informatique théorique, et notamment en théorie des langages formels, une grammaire algébrique est en forme normale de Greibach (en anglais, Greibach normal form ou GNF) si les membres droits de ses règles commencent tous par un symbole terminal, suivi éventuellement d'une ou plusieurs variables. Une variante permet une règle additionnelle pour engendrer le mot vide s'il fait partie du langage. Cette forme normale porte le nom de Sheila Greibach qui l'a introduite et a prouvé son existence.
Noam ChomskyNoam Chomsky ( ), né le à Philadelphie, est un linguiste américain. Professeur émérite de linguistique depuis 2002 au Massachusetts Institute of Technology, où il a enseigné depuis 1955, il fonde la linguistique générative. Il s'est fait connaître du grand public, à la fois dans son pays et à l'étranger, par son parcours d'intellectuel engagé de tendance socialiste libertaire et anarchiste.
Computational complexityIn computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.
