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...
Soit L⊆X∗L⊆X∗L \subseteq X^{\ast} un langage, puis nous définissons la congruence syntaxique comme u∼v:⇔∀x,y∈X∗:xuy∈L↔xvy∈Lu∼v:⇔∀x,y∈X∗:xuy∈L↔xvy∈L u \sim v :\Leftrightarrow \forall x, y\in X^{\ast} : xuy \in L \leftrightarrow xvy \in L et le quotient monoïde est appelé monoïde syntaxique de...
Reg⊆NC1Reg⊆NC1\mathsf{Reg} \subseteq \mathsf{NC^1}RegReg\mathsf{Reg}TC0⊈RegTC0⊈Reg\mathsf{TC^0} \not\subseteq \mathsf{Reg}Reg⊆TC0Reg⊆TC0\mathsf{Reg} \subseteq \mathsf{TC^0}NC1⊈TC0NC1⊈TC0\mathsf{NC^1}\not\subseteq\mathsf{TC^0}Reg⊈TC0Reg⊈TC0\mathsf{Reg} \not\subseteq \mathsf{TC^0} Y a-t-il un...
Que sait-on de la classe des langages reconnus par les automates finis ayant le même état initial et acceptant? Il s'agit d'un sous-ensemble approprié des langues régulières (puisque chaque langue de ce type contient la chaîne vide), mais à quel point est-elle faible? Existe-t-il une...
Dans le cadre d'apprentissage des automates d'Angluin , un étudiant vise à apprendre une langue régulière en posant deux types de questions à son professeur:L ⊆ Σ∗L⊆Σ∗L\subseteq \Sigma^* Requêtes de mots: étant donné , ?w ∈ Σ∗w∈Σ∗w\in \Sigma^*w ∈ Lw∈Lw\in L Requêtes d'équivalence: étant donné un...
Je veux définir une notion de "proximité" entre deux langages réguliers de mots finis dans (et / ou des mots infinis dans ). L'idée de base est que nous voulons que deux langues soient proches si elles ne diffèrent pas par beaucoup de mots. Nous pourrions également utiliser la distance d'édition...
Je m'intéresse au problème classique INCLUSION DE LA LANGUE RÉGULIÈRE. Étant donné une expression régulière , nous notons L ( E ) le langage régulier qui lui est associé. (Les expressions régulières sont sur un alphabet fixe Σ , avec les opérations union, Kleene-star et concaténation.)EEEL (...
Cette question est liée à une question récente de Janoma . Contexte Dans la programmation par contraintes, une régulière contrainte globale ccc sur un domaine DDD est une paire (s,M)(s,M)(s, M) avec sss un tuple de variables (la portée) et MMM DFA sur le domaine DDD . Une affectation θθ\theta à sss...
Je comprends que les affirmations suivantes sont vraies: Deux dérivations distinctes d'une chaîne dans un CFG donné peuvent parfois attribuer le même arbre d'analyse à la chaîne. Lorsqu'il existe des dérivations d'une chaîne dans un CFG donné qui attribuent différents arbres d'analyse, le CFG est...
Les transducteurs considérés ici sont ceux que Wikipedia appelle les transducteurs à états finis . Le comportement d'un transducteur , qui est la relation qu'il calcule, est écrit : un mot est une sortie pour ssi .[ T ] y x x [ T ] yTTT[ T][T][T]yyyXxxx [ T] yx[T]yx[T]y Question: Le problème...
Un DFA ou un NFA lit une chaîne d'entrée avec une seule tête, se déplaçant de gauche à droite. Il semble naturel de s'interroger sur les machines à états finis qui ont plusieurs têtes , chacune se déplaçant à travers l'entrée de gauche à droite, mais pas nécessairement au même endroit dans l'entrée...
Les automates bornés linéaires non déterministes à visite bornée ne reconnaissent-ils que les langues régulières? Par un automate borné linéaire non déterministe (nLBA), je veux dire une machine de Turing non déterministe à bande unique où l'entrée est "rembourrée" avec des marqueurs de fin aux...
Soit une langue, et définissons par ssi . Je recherche une référence pour:L ⊆ A∗L⊆A∗L \subseteq A^*f L ( x , y ) = 1 x ⋅ y ∈ LFL: A∗× A∗→ { 0 , 1 }fL:A∗×A∗→{0,1}f_L\colon A^* \times A^* \to \{0, 1\}FL( x , y) = 1fL(x,y)=1f_L(x, y) = 1x ⋅ y∈ Lx⋅y∈Lx\cdot y \in L Proposition. est régulier si la...
Pour une langue fixe sur un alphabet A , considérons le problème suivant, que j'appelle L -INTERLEAVING :LLLAAALLL Entrée: deux mots u,v∈A∗u,v∈A∗u, v \in A^* Rendement: s'il existe un entrelacement de et v , qui est en L .uuuvvvLLL Ici, un entrelacement de deux mots et v est un mot w qui peut être...
Étant donné un DFA complet A=(Q,Γ,δ,F)A=(Q,Γ,δ,F)A=(Q, \Gamma, \delta, F) , nous pouvons définir une collection de fonctions fafaf_a pour chacune a∈Γa∈Γa\in \Gamma et avec fa:Q→Qfa:Q→Qf_a:Q\rightarrow Q , fa(q)=δ(q,a)fa(q)=δ(q,a)f_a(q)=\delta(q, a) . On peut généraliser cette notion à un mot...
Soit un alphabet fini. Pour un langage donné le monoïde syntaxique est une notion bien connue en théorie formelle du langage. De plus, un monoïde reconnaît un langage ssi il existe un morphisme tel que .L ⊆ A ∗ M ( L ) M L φ : A ∗ → M L = φ - 1 ( φ ( L ) ) )UNEAAL ⊆ A∗L⊆UNE∗L \subseteq A^{\ast} M(...