Questions sur la théorie des expressions régulières, à la fois au sens de la définition originale de Kleene et des expressions régulières POSIX.
Je pense au problème suivant: je veux trouver une expression régulière qui correspond à un ensemble particulier de chaînes (par exemple, des adresses électroniques valides) et ne correspond à aucune autre (adresses électroniques non valides). Supposons que par expression régulière, nous entendons...
Demandez même à une personne ayant une formation en informatique ce qu’est une expression régulière et la réponse ira probablement au-delà de la contrainte d’être à la portée d’un automate à états finis. Par exemple, l'expression «expression régulière» /^1?$|^(11+?)\1+$/ créé par une personnalité...
Il est bien connu qu'une expression régulière peut être reconnue par un automate fini non déterministe de taille proportionnelle à l'expression régulière, ou par une FA déterministe qui est potentiellement exponentiellement plus grande. De plus, étant donné une chaîne et une expression régulière ,...
Je me demandais s'il y avait un `` meilleur '' algorithme (j'expliquerai dans quel sens) pour partir d'un DFA et construire une expression régulière r telle que L ( A ) = L ( r ) , que celle du livre de Hopcroft et Ullman (1979). Dans ce document, les ensembles R k i j sont utilisés pour...
Pourquoi les langages réguliers (et à partir de ces expressions régulières) sont-ils appelés "réguliers"? Il y a beaucoup de régularité également dans les langues sans contexte et d'autres types de langues. Je suppose que, au début, l'adjectif "régulier" a été utilisé pour différencier ce type de...
Outre la complexité de communication (déterministe) d'une relation , une autre mesure de base pour la quantité de communication nécessaire est le numéro de partition de protocole . La relation entre ces deux mesures est connue jusqu'à un facteur constant. La monographie de Kushilevitz et Nisan...
Il est bien connu que le problème suivant est PSPACE-complete: Étant donné l'expression régulière , ?L ( β ) = Σ ∗ββ\betaL ( β) = Σ∗L(β)=Σ∗L(\beta) = \Sigma^* Qu'en est-il de la détermination de l'équivalence avec d'autres expressions régulières (fixes) ?αα\alpha Étant donné l'expression régulière...
La plupart des implémentations modernes d'expressions régulières, telles que celles en perl ou .NET, vont au-delà de la définition informatique classique des REGEX avec des fonctionnalités comme lookahead et lookbehind. Ces fonctionnalités leur permettent-elles d'analyser des instructions qui ne...
Je me demandais si la spécification JSON définissait un langage régulier. Cela semble assez simple, mais je ne sais pas comment le prouver moi-même. La raison pour laquelle je demande, c'est parce que je me demandais si l'on pouvait utiliser des expressions régulières pour analyser efficacement...
Il y a vingt ans, j'ai construit un package d'expressions régulières qui comprenait des conversions d'expressions régulières vers une machine à états finis (DFA) et pris en charge une multitude d'opérations d'expressions régulières fermées (Kleene star, concatenation, reverse, set operations,...
La hauteur d'étoile (généralisée) d'une langue est l'imbrication minimale des étoiles de Kleene requise pour représenter la langue par une expression régulière étendue. Rappelons qu'une expression régulière étendue sur un alphabet fini satisfait ce qui suit:AAA (1) et a sont des expressions...
Il est connu que minimiser la taille d'une expression régulière est PSPACE-complete même si nous avons un DFA comme spécification du langage . Quels sont les résultats si la langue est finie? On peut considérer ce problème dans deux modèles: L'entrée correspond à toutes les chaînes du langage, et...
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...
Inspiré par cette question , je suis curieux de savoir ce qui suit: Quelle est la pire des situations pour vérifier si un DFA donné accepte le même langage qu'une expression régulière donnée? Est-ce connu? L'espoir serait que ce problème soit en P - qu'il existe un algorithme polynomial dans la...
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 (...
Tous mes manuels utilisent le même algorithme pour produire un DFA avec une expression régulière: créez d'abord un NFA qui reconnaît le langage de l'expression régulière, puis, en utilisant la construction du sous-ensemble (aka "powerset"), convertissez le NFA en un DFA équivalent ( en minimisant...
J'essaie de dresser une taxonomie d'algorithmes pour transformer des expressions régulières en automates afin d'effectuer des tests empiriques de leurs propriétés de complexité dans des domaines spécifiques. Je connais plusieurs des plus grands noms, par exemple, Thompson "Algorithme de recherche...
Je me demandais quels ensembles de langues sont générés par les restrictions des expressions régulières. Supposons que toutes les restrictions aient un symbole constant pour chaque élément de et de concaténation. Ensuite, huit classes peuvent être formées par la présence ou l'absence de complément...