Je suis coincé à résoudre le prochain exercice: Faire valoir que si est sans contexte et R est régulier, alors L / R = { w ∣ ∃ x ∈ RLLLRRR (c'est-à-dire lebon quotient) est sans contexte.L/R={w∣∃x∈Rs.twx∈L}L/R={w∣∃x∈Rs.twx∈L}L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\} Je sais qu'il...
La grammaire non contextuelle suivante présente une ambiguïté de type "balançant le reste" (imaginez que représente et b représente et c représente un autre type d'instruction ou de bloc): Saaaif expr thenbbbelseccc Par exemple,aacbcpeut être analysé comme(a(acbc))ou comme(a(ac)bc)(c'est le mot...
Je me demandais récemment ce qui se passerait si nous permettions aux grammaires sans contexte d'avoir un nombre infini de règles. De toute évidence, si nous permettions arbitrairement de tels ensembles infinis de règles, chaque langue sur un alphabet pourrait être décrite par un CFG avec . Mais...
Dans l'article Parsing Expressions by Recursive Descent de Theodore Norvell (1999), l'auteur commence par la grammaire suivante pour les expressions arithmétiques: E --> E "+" E | E "-" E | "-" E | E "*" E | E "/" E | E "^" E | "(" E ")" | v ce qui est assez mauvais, car il est ambigu et...
Au collège, nous avons appris la théorie du calcul en général et les machines de Turing plus spécifiquement. L'un des grands résultats théoriques est qu'au prix d'un alphabet potentiellement grand (symboles), vous pouvez réduire le nombre d'états à seulement 2. Je cherchais des exemples de...
Existe-t-il un ensemble de règles ou de méthodes pour convertir une grammaire sans contexte en automates push down? J'ai déjà trouvé des diapositives en ligne mais je n'ai pas pu les comprendre. Dans la diapositive 10, il parle de certaines règles. Quelqu'un pourrait-il expliquer...
J'ai récemment discuté avec un ami d'un site Web qui proposait des défis d'expression régulière, correspondant principalement à un groupe de mots avec une propriété spéciale. Il cherchait une expression régulière qui correspond à des chaînes comme ||||||||où le nombre de |est premier. Je lui ai...
En classe cette semaine, nous avons découvert les LFC et leurs propriétés de fermeture. J'ai vu des preuves d'union, d'intersection et de compliment, mais pour le renversement, mon conférencier vient de dire que c'était fermé. Je voulais voir la preuve, donc je cherchais depuis quelques jours, mais...
Comment puis-je montrer que le problème de décider si un PDA accepte une chaîne du formulaire { w! w ∣ w ∈ { 0 , 1}∗}{w!w∣w∈{0,1}∗}\{ w!w \mid w \in \{ 0, 1 \}^*\} est indécidable? J'ai essayé de réduire ce problème à un autre indécidable, par exemple si deux grammaires sans contexte acceptent la...
Est la langue L = { a , b}∗∖ { (unenbn)n∣ n ≥ 1 }L={a,b}∗∖{(anbn)n∣n≥1}L = \{a,b\}^* \setminus \{(a^nb^n)^n\mid n \geq1 \} sans contexte? Je crois que la réponse est que ce n'est pas une LFC, mais je ne peux pas le prouver par le lemme d'Ogden ou le lemme de
Est la langue L={0n1m∣n and m are co-prime}L={0n1m∣n and m are co-prime} L = \{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\} sans contexte? Je suppose que ce n'est pas sans contexte car il semble trop compliqué pour un PDA de décider si 2 nombres sont co-amorcés ou non. J'ai essayé...
Selon ce graphique , les DCFL sont fermés sous inversion. Cependant, je ne suis pas convaincu que la preuve intuitive (inversant les flèches de la machine à états finis contrôlant et commutant les poussées et les pops) pour cela semble dépendre du non-déterminisme dans le choix de la transition...
Définir l' équivalence de Nérode sur une langueL⊆Σ∗L⊆Σ∗L \subseteq \Sigma^{*} comme u∼Lvu∼Lvu \sim_L v ssi uw∈L⇔vw∈Luw∈L⇔vw∈Luw \in L \Leftrightarrow vw \in L pour chaque w∈Σ∗w∈Σ∗w \in \Sigma^{*}. L'équivalence Nerode ∼L∼L{\sim}_L a un nombre fini de classes d'équivalence précisément lorsque...