Quand une expression rationnelle n'est-elle pas une expression régulière?

9

Depuis que j'étudie pour mon cours universitaire de langues officielles, je suis tombé sur ces messages fascinants ( One Two ) qui décrivent comment trouver un nombre premier à l'aide d'une expression rationnelle . Comme je l'ai dit, une expression rationnelle , pas une expression régulière . Puisqu'une expression régulière peut correspondre à des chaînes calculées par un automate à états finis et que la recherche d'un nombre premier ne peut pas être effectuée par un FSA, l'expression rationnelle affichée dans le billet de blog n'est pas entièrement une expression régulière, car elle effectue un retour en arrière pour correspondre à la chaîne.

Comme je n'ai jamais vraiment utilisé d'expression régulière, maintenant, ma question:

Comment puis-je reconnaître immédiatement une expression rationnelle à partir d'une "vraie" expression régulière simplement en la regardant?

Définitions: Par expression régulière, je me réfère à la notion telle que définie dans les langages formels. Par regexp, je veux dire la notion supportée par les langages de programmation modernes; la syntaxe regexp contient souvent des fonctionnalités supplémentaires, telles que les références arrières. Les expressions régulières telles que vues dans les langages de programmation sont strictement plus puissantes que les expressions régulières de style de langage formel.

peperunas
la source
5
L'expression régulière n'est qu'une abréviation d'expression régulière. Le calcul des nombres premiers est basé sur un hack Perl, pas sur des expressions régulières.
1
C'est assez simple. Les langues régulières utilisent la concaténation, la répétition et l'alternance. Chaque fois qu'un moteur prend en charge quelque chose qui n'est pas équivalent à ceux-ci, il n'est pas régulier.
Kilian Foth
1
Questions connexes: 1 , 2 , 3 .
Raphael
@Yannis Si vous sautez par-dessus la clôture vers CS, ce n'est plus vrai. Les expressions régulières telles que vues dans les langages de programmation sont strictement plus puissantes que les expressions régulières (style de langage formel), et la forme courte "regexp" est par convention (je ne sais pas à quel point elle est répandue) utilisée pour les premières, pas pour les secondes. gentil.
Raphael
@KilianFoth Ce n'est pas vraiment une description utile, cependant. Par exemple, vous pouvez ajouter la négation (ou, en fait, tout ensemble fini de connecteurs booléens) aux expressions régulières sans augmenter leur puissance.
David Richerby

Réponses:

13

tl; dr backrefs.

Dès qu'il y a un \1(ou n'importe quel nombre qui n'est pas utilisé pour échapper à l'unicode) dans l'expression régulière, ce n'est pas une expression régulière.

Backrefs vous permet de faire correspondre (a+)b\1ce qui correspond à n fois asuivi de b suivi de n fois apour n> 1. Ce n'est pas une langue régulière (c'est l'enfant affiche d'une langue non régulière).

Il est nécessaire et presque suffisant que le backref fasse référence à un groupe qui contient une expression rationnelle qui correspond à une chaîne arbitrairement longue ou qu'il contient un *ou +. La seule exception (que j'ai trouvée) d'une expression rationnelle de la forme (A)B\1où A est un langage fini (pourrait être remplacée par une énumération de tous les mots qui les accepte). Vous pouvez le convertir en word1+Bword1|word2+Bword2etc. car A est fini.

Les groupes de recherche ne suppriment pas la régularité de l'expression régulière. A(?=B)Cest la section transversale des expressions rationnelles AB.*et ACet la section transversale de 2 langues régulières est régulière. L'anticipation négative est similaire, sauf en utilisant le complément de B.*(les compléments de langues régulières étant réguliers). Lookbehind est exactement le même que A(?<=B)Cla coupe transversale de ACet .*BC.

monstre à cliquet
la source
Est-ce nécessaire et suffisant? Il me semble (a)\1que, tout en utilisant un backref, est équivalent aaet donc trivialement régulier. Je me demande également si les assertions d'anticipation peuvent utiliser pour reconnaître les langues non régulières.
MSalters
1
@MSalters: Si vous voulez devenir vraiment technique, ce (a)\1n'est pas une expression régulière, mais reconnaît un langage régulier.
Jörg W Mittag