Questions sur les expressions régulières, un formalisme pour décrire les langages réguliers.
Convertir des expressions régulières en NFA (minimales) acceptant le même langage est facile avec des algorithmes standard, tels que celui de Thompson . L’autre direction semble être plus fastidieuse, cependant, et les expressions résultantes sont parfois désordonnées. Quels algorithmes existe-t-il...
Comme on le voit dans cette récente bande XKCD et ce récent article de blogde Peter Norvig (et une histoire de Slashdot mettant en vedette ce dernier), "regex golf" (qui pourrait mieux être appelé le problème de séparation des expressions régulières) est le casse-tête de définir l'expression...
Cette question a été migrée depuis Stack Overflow car il est possible d'y répondre sur Computer Science Stack Exchange. Migré il y a 7 ans . J'ai créé un lexer et un analyseur d'expressions régulières simples pour prendre une expression régulière et générer son arbre d'analyse. La création d'un...
Voici une conjecture pour les expressions régulières: Pour l'expression régulière , laissez la longueurêtre le nombre de symboles qu'il contient, en ignorant les parenthèses et les opérateurs. Par exemple| R | | 0 ∪ 1 | = | ( 0 ∪ 1 ) ∗ | = 2RRR| R ||R||R|| 0∪1 | = |( 0 ∪ 1 )∗| =2|0∪1|=|(0∪1)∗|=2|0...
J'ai cherché sur le net une réponse à cette question et il semble que tout le monde connaisse implicitement la réponse sauf moi. On peut supposer que cela est dû au fait que les seules personnes qui s’en soucient sont celles qui ont fait des études supérieures sur le sujet. D'un autre côté, j'ai...
Comme le titre l'indique, j'ai passé quelques heures le week-end dernier à essayer de résumer la classe de langages correspondant aux expressions régulières compatibles Perl, à l' exclusion de tout opérateur de correspondance qui permet d'exécuter du code arbitraire à l'intérieur du modèle . Si...
Réglage: expressions régulières avec références arrières langue unaire (alphabet à 1 symbole) Le problème suivant est-il décidable dans ce paramètre: Étant donné une expression régulière avec des références arrières, définit-elle un langage régulier? Par exemple, (aa+)\1définit une langue...
Si j'ai une grammaire de type 3, elle peut être représentée sur un automate déroulant (sans faire aucune opération sur la pile) afin que je puisse représenter des expressions régulières en utilisant des langages sans contexte. Mais puis-je savoir si une grammaire de type 3 est , L L ( 1 ) , S L R (...
Apparemment, les attaques ReDos exploitent les caractéristiques de certaines expressions régulières (autrement utiles) ... provoquant essentiellement une explosion de chemins possibles à travers le graphique défini par le NFA. Est-il possible d'éviter de tels problèmes en écrivant une expression...
Il semble que les «expressions régulières de base» telles que définies par POSIX.1-2008 ne prennent pas en charge l'alternance a|b(bien que certaines implémentations grep reconnaissent la version échappée \|). Les langues régulières étant fermées par union par définition, cela signifie-t-il que...
Le problème Il n'y a pas de moyen facile d'obtenir une permutation avec une expression régulière. Permutation: obtenir un mot ("aabc") dans un autre ordre, sans changer le nombre ou le type de lettres.w=x1…xnw=x1…xnw=x_1…x_n Regex: expression régulière. Pour vérification: "Permutations d'expression...
Je me moquais de l'autre jour sur ce site Web: http://regexcrossword.com/ et cela m'a fait me demander quelle était la meilleure façon de le résoudre. Pouvez-vous résoudre le problème suivant en temps polynomial ou est-il NP-difficile? Étant donné une grille NxM avec N expressions régulières pour...
J'ai trouvé que si je ne comprends pas l'étymologie derrière un terme cs / programmation, cela signifie généralement que j'ai manqué ou mal compris un concept sous-jacent important. Je ne comprends pas pourquoi l'étoile Kleene est aussi appelée la fermeture Kleene. Est-ce lié aux fermetures de...
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...
L'objectif est de créer DFA à partir d'une expression régulière et l'utilisation de "Exp régulière> NFA> Conversion DFA" n'est pas une option. Comment faut-il s'y prendre? J'ai posé cette question à notre professeur mais il m'a dit que nous pouvions utiliser l'intuition et a gentiment refusé...
Je suis nouveau dans les automates et je n'ai reçu une brève introduction aux expressions régulières qu'hier. J'ai lu les différentes règles qui définissent une expression régulière. Mais je suis incapable de faire la différence entre les expressions régulières et la grammaire d'une langue (on ne...
Je pensais que toutes les langues régulières pouvaient être exprimées avec des expressions régulières (si une langue est régulière, elle peut être exprimée avec regex), mais on m'a dit que vous avez besoin des trois opérations régulières (concaténation, union et étoile) pour cela tenir. Par...
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...
Étant donné deux expressions régulières arbitraires, existe-t-il un algorithme "efficace" pour déterminer si elles correspondent au même ensemble de chaînes? Plus généralement, peut-on calculer la taille de l'intersection des deux jeux de correspondance? Quels algorithmes sont là pour le faire et...
Si je comprends bien, les NFA ont le même pouvoir expressif que les expressions régulières. Souvent, la lecture d'expressions régulières équivalentes dans NFA est facile: vous traduisez des cycles en étoiles, des jonctions comme alternatives, etc. Mais que faire dans ce cas: [ source ] Les cycles...