Questions sur l'ensemble des langages (équivalents) décrits par des grammaires hors contexte ou acceptés par des automates de refoulement (non déterministes).
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....
Le contexte linguistique suivant est-il libre? L={uxvy∣u,v,x,y∈{0,1}+,|u|=|v|,u≠v,|x|=|y|,x≠y}L={uxvy∣u,v,x,y∈{0,1}+,|u|=|v|,u≠v,|x|=|y|,x≠y}L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} Comme indiqué par sdcvvc, un mot dans cette langue peut également être...
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 }...
Étant donné une grammaire sans contexte G, il existe un automate N non déterministe à refoulement qui accepte exactement le langage que G accepte. (et vice versa) Il peut également exister un automate déterministe à refoulement qui accepte exactement le langage que G accepte également. Cela dépend...
Lorsque l'on considère les modèles de calcul des machines, la hiérarchie de Chomsky est normalement caractérisée par (dans l'ordre), les automates finis, les automates déroulants, les automates liés linéaires et les machines de Turing. Pour le premier et le dernier niveau 1 (langages réguliers et...
Les langages sans contexte ne sont pas fermés sous complément, nous le savons. Pour autant que je sache, les langages sans contexte qui sont un sous-ensemble de pour certaines lettres sont fermés sous complément (!?) a , ba∗b∗a∗b∗a^*b^*a,ba,ba,b Voici mon argument. Chaque langue CF a une image...
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,...
Existe-t-il un algorithme / une procédure systématique pour tester si une langue est hors contexte? En d'autres termes, étant donné un langage spécifié sous forme algébrique (pensez à quelque chose comme ), testez si le langage est hors contexte ou non. Imaginez que nous écrivons un service Web...
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...
Notez qu'il s'agit d'une question liée à l'étude dans un cours de CS dans une université, ce n'est PAS des devoirs et peut être trouvé ici sous l'examen d'automne 20112. Voici les deux questions que je regarde d'un examen passé. Ils semblent être liés, le premier: Laisser FINITECFG={<G>∣G is...
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...
Je me demande si cela est encore possible, puisque {anbncn∣n≥0}∉CFL{anbncn∣n≥0}∉CFL\{a^n b^n c^n \mid n \geq 0\} \not\in \mathrm{CFL} . Par conséquent, un PDA qui peut distinguer un mot w∈{anbncn∣n≥0}w∈{anbncn∣n≥0}w\in\{a^n b^n c^n \mid n \geq 0\} du reste de {a∗b∗c∗}{a∗b∗c∗}\{a^*b^*c^*\} pourrait...
Donc, fondamentalement, L satisfait aux conditions du lemme de pompage pour les CFL mais n'est pas un CFL (ce qui est possible selon la définition du
Soit GGG une grammaire sans contexte. Une chaîne de terminaux et de nonterminals est dit être une forme propositionnelle de si vous pouvez l' obtenir en appliquant des productions de zéro fois ou plus au symbole de début de . Let l'ensemble des formes phrastiques de
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...
Je sais qu'il existe des langages non réguliers, de sorte que est régulier, mais tous les exemples que je peux trouver sont sensibles au contexte mais pas libres de contexte.L∗L∗L^* Au cas où il n'y en aurait pas comment le
J'ai un problème avec cet exercice: Soit G la grammaire ambiguë suivante pour le λ-calcul: E → v | λv.E | EE | (E) où E est le symbole non terminal unique, λv.E représente l'abstraction par rapport à la variable v dans E et EE représente l'application. Définissez une grammaire LL (1) G ′ telle que...