Dans la préface de ses livres très influents Automates, Langages et Machines (Volumes A, B), Samuel Eilenberg a promis de façon alléchante les Volumes C et D traitant "d'une hiérarchie (appelée hiérarchie rationnelle) des phénomènes non rationnels ... utilisant des relations rationnelles comme un...
Dans de nombreux articles impliquant des grammaires sans contexte (CFG), les exemples de telles grammaires présentés ici admettent souvent des caractérisations faciles du langage qu'elles génèrent. Par exemple: S→aaSbS→aaSbS \to a a S b S→S→S \to génère {a2ibi|i≥0}{a2ibi|i≥0}\{ a^{2i} b^i | i \geq...
Pratiquement, pour un langage qui peut éventuellement être compilé / transformé en instructions au niveau du système, est-il nécessaire que ce soit une grammaire sans contexte? ex: tous les langages de programmation / script sont-ils des grammaires sans contexte? Java est basé sur des CFG, mais...
En bricolant avec l'analyse LR non canonique, j'ai pensé à une méthode d'analyse (avec des tables de taille infinie, ce qui la rend peu pratique ) capable d'analyser exactement les grammaires sans ambiguïté en temps , et je me suis demandé s'il était possible de faire mieux :O(n2)O(n2)O(n^2) Toutes...
Je recherche des langages qui ne sont "probablement pas sans contexte" mais nous ne sommes pas en mesure de le (dé) prouver en utilisant des techniques standard connues. Y a-t-il une enquête récente sur le sujet ou une section de problème ouvert d'une conférence récente? Il n'y a probablement pas...
Notons wnwnw_n le nombre de mots de longueur nnn dans une langue sans contexte (éventuellement ambiguë). Que sait-on de wnwnw_n ? Je suis sûr que cela a été beaucoup étudié, mais je n'ai rien trouvé du tout
Étant donné les expressions régulières , existe-t-il des limites non triviales à la taille de la plus petite grammaire sans contexte pour R 1 ∩ ⋯ ∩ R n ?R1, … , RnR1,…,RnR_1, \dots, R_nR1∩ ⋯ ∩ RnR1∩⋯∩RnR_1 \cap \cdots \cap
Il est bien connu que le problème d'équivalence est indécidable pour les langages généraux sans contexte. Cependant, toutes les preuves de ce fait que je connais semblent impliquer des grammaires ambiguës sans contexte. Pour cette raison, je voudrais demander si l'on sait si le problème reste...
J'ai lu quelque part qu'une machine Turing ne peut pas calculer cela et c'est donc indécidable mais pourquoi? Pourquoi est-il impossible sur le plan informatique pour une machine de générer l'arbre d'analyse et de prendre une décision? Peut-être que je me trompe et que cela peut être...
Il existe une multitude d'algorithmes qui peuvent analyser une grammaire sans contexte en temps . En utilisant la multiplication matricielle, on peut même aller plus vite asymptotiquement que cela.O ( n3)O(n3)O(n^3) Cependant, tous les algorithmes d'analyse syntaxique des CFG arbitraires que je...
Dans le livre de Sakarovitch sur la théorie des automates, il est écrit dans l'introduction de la section sur les logiques du groupe libre que le matériel qui y est présenté jette "les bases d'une théorie véritablement mathématique des langages sans contexte". Néanmoins, cela n'est pas rendu...
Une phrase de permutation est une extension des définitions de grammaire sans contexte standard (E) BNF: une phrase de permutation contient n productions (ou de manière équivalente, non terminales) A 1 à A n . À la position de la phrase de permutation, nous aimerions voir chacune de ces productions...
Je me demande s'il y a des articles ou des recherches traitant des automates visiblement pushdown, mais permettant aux mots, plutôt qu'aux lettres simples, d'être poussés sur la pile. Alternativement, une construction qui a permis de symboles d'être poussé sur ϵϵ\epsilon -Transitions pourrait...
Dans la description formelle des automates déterministes de refoulement, ils autorisent mouvements, où la machine peut faire apparaître ou pousser des symboles sur la pile sans lire un symbole de l'entrée. Si ces mouvements ϵ ne sont pas autorisés et que la pile ne peut être modifiée qu'une fois...
C'est une preuve standard dans les cours d'automates que pour et | Σ | ≥ 2 que S ( L ) = { w w : w ∈ L } n'est pas une langue sans contexte.L=Σ⋆L=Σ⋆L = \Sigma^\star|Σ|≥2|Σ|≥2|\Sigma| \ge 2S(L)={ww:w∈L}S(L)={ww:w∈L}S(L) = \{ww : w \in L\} Il est également vrai que pour tout fini , S ( L ) est fini...
Il serait intéressant de rassembler une liste de conditions qui impliquent qu'un langage sans contexte L est régulier, c'est-à-dire des conditions de la forme: "si un CFG / PDA donné a la propriété P, alors ses langages sont réguliers" La propriété P n'a pas à caractériser les CFG générant des...
Considérons la question naturelle suivante: étant donné un langage fini , quelle est la plus petite grammaire sans contexte générant ?LLLLLL Nous pouvons rendre la question plus intéressante en spécifiant une séquence de langues , par exemple est l'ensemble de toutes les permutations de :...
Après avoir lu la question récente "est le complément de {www∣...}{www∣...}\{ www \mid ...\} Hors -contexte?" ; Je me suis souvenu d'un problème similaire que je n'ai pas pu réfuter: Est L={ww′∣w,w′∈{0,1}∗∧|w|=|w′|∧HamDist(w,w′)>1}L={ww′∣w,w′∈{0,1}∗∧|w|=|w′|∧HamDist(w,w′)>1}L = \{ ww' \mid...
Les langages Dyck sont définis par la grammaire suivante S → S SDyck(k)Dyck(k)\mathsf{Dyck}(k) sur l'ensemble des symboles { ( 1 , … , ( k , ) 1 , … , ) k } . Langues Intuitivement Dyck sont les langues de parenthèses équilibré de k genre différent. Par exemple,
J'examine le langage de toutes les formules logiques propositionnelles satisfaisantes, SAT (pour garantir qu'il ait un alphabet fini, nous encoderions les lettres propositionnelles d'une manière appropriée [modifier: les réponses ont souligné que la réponse à la question peut ne pas être robuste...