Questions sur les machines à états avec une seule pile pour la mémoire. Ils caractérisent la classe des langages sans contexte.
Dans cette réponse, il est mentionné Un langage régulier peut être reconnu par un automate fini. Un langage sans contexte nécessite une pile et un langage sensible au contexte nécessite deux piles (ce qui revient à dire qu'il nécessite une machine Turing complète) . Je voulais savoir en ce qui...
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...
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...
É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...
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...
Le problème de savoir si deux automates déroulants reconnaissent la même langue est indécidable. Le problème de savoir si un automate pushdown reconnaît la langue vide est décidable, d'où il est également décidable s'il reconnaît une langue finie donnée. Il est indécidable que la langue acceptée...
Je me rends compte que les automates de refoulement non déterministes peuvent être une amélioration par rapport aux déterministes car ils peuvent "choisir" parmi plusieurs états et il existe des langages sans contexte qui ne peuvent pas être acceptés par un refoulement déterministe. Pourtant, je ne...
Apropois à la suggestion de Raphaël sur l' intersection de deux NPDA : Soit et A 2 NPDA pour les langues sans contexte L 1 et L 2 , respectivement. En supposant que nous savons que L = L 1 ∩ L 2 est sans contexte, pouvons-nous (effectivement) construire NPDA A pour L
Je souhaite convertir une expression régulière entrée par l'utilisateur en NFA afin de pouvoir ensuite exécuter le NFA sur une chaîne à des fins de correspondance. Quelle est la machine minimale qui peut être utilisée pour analyser des expressions régulières? Je suppose que ce doit être un automate...
Au travail, j'ai été chargé de déduire des informations de type sur un langage dynamique. Je réécris des séquences d'instructions en imbriquéeslet expressions , comme ceci: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then...
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...
Soit une chaîne d'entrée donnée comme . Ensuite, si un NFA est actuellement dans l'état (et a lu l'entrée jusqu'à l'alphabet ), puis avant de lire le symbole d'entrée suivant, le NFA se divise en deux NFA, l'un étant dans l'état r et l'autre dans s , s'il y a une transition de le type r \...
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...
Ces diapositives de cours esquissent une preuve queL = {unenbn∣ n ≥ 0 } ∪ {unenb2 n∣ n ≥ 0 }L={anbn∣n≥0}∪{anb2n∣n≥0}L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \} ne peut être accepté par aucun automate déterministe à refoulement. Malheureusement, les diapositives ne donnent...
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...
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é...
J'essaie depuis un certain temps de trouver une construction afin de pouvoir démontrer formellement qu'un PDA déterministe est fermé sous complémentation. Cependant, il arrive que chaque idée que j'ai a quelque chose qui ne correspond pas à la fin. Pourriez-vous me donner un coup de main? Le...
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...
est-il possible de minimiser les automates de refoulement? Si non, pourquoi? Est-ce parce que pour la minimisation, les classes d'équivalence doivent avoir un indice fini et nous ne pouvons pas le garantir pour
Soit A={L∣Lis one-counter and L¯ is also one-counter}A={L∣Lis one-counter and L¯ is also one-counter}A= \{L \mid L \;\text{is one-counter and \(\bar{L}\) is also one-counter} \} En clair,Deterministic one-counter⊆ADeterministic one-counter⊆A\text{Deterministic one-counter} \subseteq A Est-ce le cas...