Questions sur les grammaires formelles, descriptions génératives des langages formels.
Les gens disent souvent que les analyseurs syntaxiques LR (k) sont plus puissants que les analyseurs syntaxiques LL (k) . Ces déclarations sont vagues la plupart du temps; en particulier, devrions-nous comparer les classes pour un fixe ou l'union sur tous les k ? Alors, comment est la situation...
Appelons un langage déterministe sans contexte si et seulement si il peut être accepté par un automate push-down déterministe, et non déterministe autrement. Appelons un langage dépourvu de contexte intrinsèquement ambigu si et seulement si toutes les grammaires sans contexte qui génèrent le...
Voyant que, dans la hiérarchie de Chomsky, les langues de type 3 peuvent être reconnues par une machine à états dépourvue de mémoire externe (c'est-à-dire un automate fini), le type 2 par une machine à états à pile unique (un automate à pile) et le type 0 par une machine d'état à deux piles (ou, de...
Il existe de nombreuses définitions en ligne sur ce qu'est une grammaire sans contexte, mais rien de ce que je trouve ne satisfait mon problème principal: De quel contexte est-il libre? Pour enquêter, j'ai recherché «grammaire contextuelle» sur Google, mais je n'ai toujours pas trouvé de quoi il...
J'étudie les compilateurs depuis un certain temps et je cherche ce que l'on entend par «contexte» en grammaire et ce que cela signifie pour la grammaire d'être «sans contexte», mais sans résultat. Alors, quelqu'un peut-il
J'ai un ensemble de paires. Chaque paire est de la forme (x, y) telle que x, y appartiennent à des entiers de la plage [0,n). Donc, si le n est 4, alors j'ai les paires suivantes: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) J'ai déjà les paires. Maintenant, je dois construire une combinaison en utilisant...
Il existe de nombreuses techniques pour prouver qu'une langue n'est pas sans contexte, mais comment puis-je prouver qu'une langue est sans contexte? Quelles techniques existe-t-il pour le prouver? De toute évidence, une façon consiste à présenter une grammaire sans contexte pour la langue....
Mon problème est de savoir comment prouver qu'une grammaire est sans ambiguïté? J'ai la grammaire suivante: S→statement∣if expression then S∣if expression then S else SS→statement∣if expression then S∣if expression then S else SS → statement ∣ \mbox{if } expression \mbox{ then } S ∣ \mbox{if }...
EPAL, la langue des palindromes pairs, est définie comme la langue générée par la grammaire sans contexte suivante sans ambiguïté: S→ a aS→aaS \rightarrow a a S→ b bS→bbS \rightarrow b b S→ un SuneS→aSaS \rightarrow a S a S→ b SbS→bSbS \rightarrow b S b EPAL est le «fléau» de nombreux algorithmes...
Spécifier des langues formelles en donnant des grammaires formelles est une tâche fréquente: nous avons besoin de grammaires non seulement pour décrire les langues, mais aussi pour les analyser, ou même pour faire une science appropriée . Dans tous les cas, il est important que la grammaire soit...
Cette question a été migrée à partir de la bourse théorique de l'informatique, car elle peut être répondue sur la bourse de la science informatique. Migré il y a 7 ans . Je recherche des théories mathématiques qui traitent de la description des langages formels (ensemble de chaînes) en général et...
Dans la conception du compilateur, pourquoi la récursion gauche devrait-elle être éliminée dans les grammaires? Je lis que c'est parce que cela peut provoquer une récursion infinie, mais n'est-ce pas également vrai pour une grammaire récursive
Considérons deux grammaires contexte et et la question suivante: , c'est-à-dire, les deux grammaires sont-elles équivalentes?g1g1G_1g2g2G_2L ( G1) = L ( G2)L(g1)=L(g2)L(G_1) = L(G_2) En général, ce problème est indécidable. Cependant, si et sont des gauche (ou à droite), le problème est décidable,...
Selon cet article de Wikipedia , les grammaires illimitées sont équivalentes aux machines de Turing. L'article note que je peux convertir n'importe quelle machine Turing en une grammaire illimitée, mais il montre uniquement comment convertir une grammaire en machine Turing. Comment puis-je vraiment...
Une grammaire sans contexte peut-elle inclure des "états morts" d'un automate, tels que G = ( {a,b,c},{A,B,C} , { A → a B , B → b , B → C, C→ c C} , A )?g=({une,b,c},{UNE,B,C},{UNE→uneB,B→b,B→C,C→cC},UNE)?G = \big(\{a, b, c\}, \{A, B, C\}, \{A\to aB, B\to b, B\to C, C\to cC\}, A\big)\,? Les règles...
Si j'ai une grammaire de type 3, elle peut être représentée sur un automate déroulant (sans faire aucune opération sur la pile) afin que je puisse représenter des expressions régulières en utilisant des langages sans contexte. Mais puis-je savoir si une grammaire de type 3 est , L L ( 1 ) , S L R (...
On dit que l'intersection d'un langage L sans contexte avec un langage M normal est toujours sans contexte. J'ai compris la preuve de la construction de produits croisés, mais je ne comprends toujours pas pourquoi elle est sans contexte mais pas régulière. Le langage généré par une telle...
On peut soutenir que la plupart des langages créés pour décrire des problèmes quotidiens sont sensibles au contexte. En revanche, il est possible et pas difficile de trouver des langages qui ne sont pas récursifs ou même non récursivement énumérables. Entre ces deux types se trouvent les langages...
Définissez la langue LLL comme L = { a , b } ∗ - { w w ∣ w ∈ { a , b } ∗ }L={a,b}∗−{ww∣w∈{a,b}∗}L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\} . En d'autres termes, LLL contient les mots qui ne peuvent pas être exprimés comme un mot répété deux fois. L est LL-il sans contexte ou non? J'ai essayé de...
Selon l'article de Wikipedia , le L dans signifie "balayage de gauche à droite" et le "R" signifie "dérivation la plus à droite". Cependant, dans l'article original de Knuth sur les grammaires L R ( k ) , il définit L R ( k ) (à la page 610) comme un langage "traduisible de gauche à droite avec k...