Langage algébrique déterministe

En informatique théorique et en théorie des langages, un langage algébrique déterministe est un langage algébrique reconnu (par états finals) par un automate à pile déterministe. L'intérêt des langages déterministes est que leur analyse syntaxique se fait en temps linéaire en la longueur du mot, alors que dans un langage algébrique quelconque, la complexité est cubique, ou en tout cas se ramène à la complexité du produit matriciel, donc est en O(n2,37) où n est la longueur du mot par l'algorithme de Valiant. Tout langage algébrique déterministe peut être décrit par une grammaire LR(1) et réciproquement. Cela permet de les utiliser pour des applications pratiques. Ainsi, la plupart des langages de programmation sont des langages algébriques déterministes. Le langage est déterministe. Le langage , où est une lettre différente de , et où est le retourné de , est déterministe. La classe des langages algébriques déterministes contient strictement la classe des langages rationnels et est strictement incluse dans celle des langages algébriques, et même des langages algébriques inambigus. Le contre-exemple type de langage algébrique non déterministe est l'ensemble des palindromes. La classe des langages algébriques déterministes est close par complémentaire. Cependant : elle n'est pas close par intersection (même contre-exemple que dans le cas non déterministe) ; elle n'est pas close par union (conséquence de la clôture par complémentaire et union) ; elle n'est pas close par concaténation ; elle n'est pas close par miroir, par exemple, est algébrique déterministe mais pas . Le langage n'est pas déterministe. Le langage n'est pas déterministe sur un alphabet à au moins deux lettres. Ce langage est formé des mots dont la deuxième moitié contient au moins une occurrence de la lettre . Le langage des palindromes n'est pas déterministe.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés (11)

Cours associés (3)

Séances de cours associées (30)

COM-406: Foundations of Data Science

We discuss a set of topics that are important for the understanding of modern data science but that are typically not taught in an introductory ML course. In particular we discuss fundamental ideas an

MATH-483: Gödel and recursivity

Gödel incompleteness theorems and mathematical foundations of computer science

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 in

Compression: Inégalité de Kraft

Explique la compression et l'inégalité Kraft dans les codes et les séquences.

Grammaires sans contexte

Couvre les grammaires sans contexte, leur équivalence avec les automates pushdown et la hiérarchie des types de grammaire.

Grammaires sans contexte: Partie 2

Couvre les grammaires sans contexte, y compris la définition des symboles non terminaux et terminaux, les règles pour générer des chaînes, et le concept de dérivations.

Une grammaire formelle est un formalisme permettant de définir une syntaxe et donc un langage formel, c'est-à-dire un ensemble de mots admissibles sur un alphabet donné. La notion de grammaire formelle est particulièrement utilisée en programmation logique, compilation (analyse syntaxique), en théorie de la calculabilité et dans le traitement des langues naturelles (tout particulièrement en ce qui concerne leur morphologie et leur syntaxe).

In automata theory, a deterministic pushdown automaton (DPDA or DPA) is a variation of the pushdown automaton. The class of deterministic pushdown automata accepts the deterministic context-free languages, a proper subset of context-free languages. Machine transitions are based on the current state and input symbol, and also the current topmost symbol of the stack. Symbols lower in the stack are not visible and have no immediate effect. Machine actions include pushing, popping, or replacing the stack top.

Le palindrome (adjectif et substantif masculin), du grec / pálin (« en arrière ») et / drómos (« chemin, voie »), aussi appelé palindrome de lettres est une figure de style désignant un mot ou une phrase dont l'ordre des lettres reste le même qu'on les lise de gauche à droite ou de droite à gauche, comme dans la phrase ou encore à un accent près. Le palindrome est un cas particulier d'anacyclique (lequel est lui-même un cas particulier d'anagramme) comme « suce|écus », pour lequel la signification est la même dans les deux sens de lecture.