Je me demande s'il y a des articles ou des recherches traitant des automates visiblement pushdown, mais permettant aux mots, plutôt qu'aux lettres simples, d'être poussés sur la pile. Alternativement, une construction qui a permis de symboles d'être poussé sur ϵϵ\epsilon -Transitions pourrait...
Les automates finis sans ambiguïté (UFA) sont un type spécial d'automates finis non déterministes (NFA). Un NFA est appelé sans ambiguïté si chaque mot a au plus un chemin d'acceptation.w∈Σ∗w∈Σ∗w\in \Sigma^* Cela signifie .DFA⊂UFA⊂NFADFA⊂UFA⊂NFADFA\subset UFA\subset NFA Résultats d'automate...
Pour un langage L ⊆ Σ ^ * , définissez la congruence syntaxique ≡ de L comme la moindre congruence sur Σ ^ * qui sature L , soit: u ≡ v ⇔ (∀ x, y) [xuy ∈ L ↔ xvy ∈ L]. Définissez maintenant l' équivalence Nerode comme la congruence droite suivante: u ∼ v ⇔ (∀ x) [ux ∈ L ↔ vx ∈ L]. Soit [u] la...
Dans la description formelle des automates déterministes de refoulement, ils autorisent mouvements, où la machine peut faire apparaître ou pousser des symboles sur la pile sans lire un symbole de l'entrée. Si ces mouvements ϵ ne sont pas autorisés et que la pile ne peut être modifiée qu'une fois...
Nous disons que NFA est constamment ambigu s'il existe telle sorte que tout mot est accepté par ou (exactement) chemins.k ∈ N w ∈ Σ ∗ 0 kMMMk∈Nk∈Nk\in \mathbb{N}w∈Σ∗w∈Σ∗w\in \Sigma^*000kkk Si l'automate est constamment ambigu pour , alors est appelé FA sans ambiguïté (UFA).k = 1 MMMMk=1k=1k=1MMM...
Il existe des preuves théoriques que la construction de produits cartésiens naïfs pour l'intersection des DFA est "le meilleur que nous pouvons faire". Qu'en est-il de la concaténation de deux DFA? La construction triviale implique la conversion de chaque DFA en NFA, l'ajout d'une transition...
Contexte: Étant donné deux automates finis déterministes A et B, nous formons le produit C en laissant les états dans C être le produit cartésien des états dans A et des états dans B. Ensuite, nous choisissons les transitions, l'état initial et les états finaux de sorte que le langage accepté par C...
Soit la famille de toutes les langues sur satisfaisant la propriété de pompage des langues régulières. A savoir: pour chaque , il y a un st chaque mot , peut s'écrire sous la forme w = xyz où: 1. | y |> 0 , 2. | xy | \ le N , 3. xy ^ iz \ in L pour tout i \ ge 0 . Σ L ∈ L N ∈ N w ∈ L | w | >...
Lemme: En supposant une équivalence éta, nous avons cela (\x -> ⊥) = ⊥ :: A -> B. Preuve: ⊥ = (\x -> ⊥ x)par eta-équivalence, et (\x -> ⊥ x) = (\x -> ⊥)par réduction sous lambda. Le rapport Haskell 2010, section 6.2 spécifie la seqfonction par deux équations: seq :: a -> b -> b...
Un automate Xor non déterministe (NXA) est syntaxiquement un NFA, mais un mot est dit accepté par NXA s'il a un nombre impair de chemins d'acceptation (au lieu d'au moins un chemin d'acceptation dans le cas NFA). Il est facile de voir que pour un langage régulier fini , il existe un NFA minimal qui...
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...
Je lis " Concaténation des langues régulières et complexité descriptive " par Galina Jiraskova, 2009 sur la complexité de l'état résultant de la concaténation de deux langues régulières (par Galina Jiraskova), mais je ne comprends pas quelles seraient les implications pratiques de la complexité de...
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...
Y a-t-il une "belle" hiérarchie (peut-être finie) à l'intérieur de la classe des langues régulières ? Par gentil ici, les classes de chaque hiérarchie capturent différentes expressivités / puissance / complexité. De plus, l'appartenance à chaque classe est "joliment" démontrée par certains éléments...
Étant donné un automate A (déterministe ou non déterministe, je pense que cela n'a pas beaucoup d'importance) et un seuil n , A accepte-t-il un mot contenant au plus n lettres distinctes? (Par k lettres différentes, je veux dire que aabaa a deux lettres distinctes, a et b .) J'ai montré que ce...
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...
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...
En enseignant comment implémenter les FSM à l'aide de circuits logiques synchrones, j'ai remarqué une coïncidence intrigante: dans le monde théorique CS et dans le monde de l'électrotechnique, "état" est généralement noté (et l'espace d'état ). J'ai d'abord posé une question sur EE.sx , mais en...
Donc, j'ai environ 100-200 matrices booléennes carrées très clairsemées avec une longueur de côté ~ plusieurs dizaines, et j'ai besoin de calculer leur produit. Je sais que si je les multiplie en série, le produit restera généralement aussi clairsemé à chaque étape. Existe-t-il des algorithmes de...
Les automates à états finis résiduels (RFSA, définis dans [DLT02]) sont des NFA qui ont de belles fonctionnalités en commun avec les DFA. En particulier, il y a toujours une RFSA de taille minimale canonique pour chaque langue régulière, et la langue reconnue par chaque état dans la RFSA est un...