La réponse à la question que vous posez, qui est de savoir si une classe plus large de langues que les langues peuvent être reconnus avec des expressions régulières augmentée par lookaround, n'est pas.
Une preuve en est relativement simple, mais un algorithme pour traduire une expression régulière contenant lookarounds dans l'une sans est en désordre.
Première: notez que vous pouvez toujours annuler une expression régulière (sur un alphabet fini). Étant donné un graphe d'état de l'automate qui reconnaît le langage généré par l'expression, vous pouvez simplement échanger tous les acceptant les états de non-acceptation des états pour obtenir un FSA, qui reconnaît exactement la négation de cette langue, pour lesquels il existe une famille de l'équivalent des expressions régulières.
Deuxièmement: parce que les langages réguliers (et donc des expressions régulières) sont fermés en vertu de la négation ils sont également fermé en vertu de l'intersection depuis Une intersection B = neg ( neg(A) de l'union neg(B)) par de Morgan lois. En d'autres mots, deux expressions régulières, vous pouvez trouver une autre expression régulière qui correspond à la fois.
Cela vous permet de simuler lookaround expressions. Par exemple, u(?=v)w correspond seulement les expressions qui correspondent aux uv et à l'université du wisconsin.
Pour d'anticipation négatif, vous avez besoin de l'expression régulière équivalente de l'ensemble de la théorie des A\B, qui est juste Un intersect (neg B) ou, de manière équivalente neg (neg(A) de l'union B). Ainsi pour tous les regular expressions r et s, vous pouvez trouver une expression régulière r-s qui correspond à ces expressions qui correspondent à r, ce qui ne correspond pas à s. En anticipation négatif termes: u(?!v)w correspond seulement les expressions qui correspondent à uw - uv.
Il y a deux raisons pour lesquelles lookaround est utile.
D'abord, parce que la négation d'une expression régulière peut entraîner dans quelque chose de beaucoup moins bien rangé. Par exemple q(?!u)=q($|[^u]).
Deuxièmement, les expressions régulières en faire plus que les expressions de correspondance, ils consomment aussi des caractères d'une chaîne - ou du moins c'est la façon dont nous aimons à penser à eux. Par exemple en python je me soucie de la .start() et .end(), donc bien sûr:
>>> re.search('q($|[^u])', 'Iraq!').end()
5
>>> re.search('q(?!u)', 'Iraq!').end()
4
Troisièmement, et je pense que c'est plutôt une raison importante, la négation des expressions régulières ne soulevez pas bien sur la concaténation. neg(a)neg(b) n'est pas la même chose que neg(ab), ce qui signifie que vous ne pouvez pas traduire un lookaround hors du contexte dans lequel vous le trouvez - vous avez à traiter de l'ensemble de la chaîne. Je suppose que ça le rend désagréable pour les gens à travailler et les pauses de la réaction des gens sur des expressions régulières.
J'espère avoir répondu à votre question théorique (ses tard dans la nuit, donc pardonnez-moi si je suis pas clair). Je suis d'accord avec le commentateur qui a dit que ce n'est avoir des applications pratiques. J'ai rencontré beaucoup le même problème lorsque vous essayez de gratter quelques très compliqué de pages web.
MODIFIER
Mes excuses pour ne pas être plus clair: je ne crois pas que vous pouvez donner une preuve de la régularité des expressions régulières + lookarounds par induction structurelle, mon u(?!v)w exemple était censé être juste que, un exemple, et facile. La raison structurelle de l'induction ne fonctionne pas est parce que lookarounds se comporter dans un non-composition: le point que j'essayais de faire au sujet des négations ci-dessus. Je soupçonne directe de la preuve formelle va avoir beaucoup de problèmes. J'ai essayé de penser à un moyen facile de le montrer, mais ne peut pas venir avec un arrêt sur le dessus de ma tête.
Pour illustrer, à l'aide de Josh premier exemple d' ^([^a]|(?=..b))*$ c'est l'équivalent de 7 état DONNE à tous les états d'accepter:
A - (a) -> B - (a) -> C --- (a) --------> D
Λ | \ |
| (not a) \ (b)
| | \ |
| v \ v
(b) E - (a) -> F \-(not(a)--> G
| <- (b) - / |
| | |
| (not a) |
| | |
| v |
\--------- H <-------------------(b)-----/
L'expression régulière de l'état d'Un seul ressemble:
^(a([^a](ab)*[^a]|a(ab|[^a])*b)b)*$
En d'autres termes, toute expression régulière que vous allez obtenir en éliminant lookarounds sera en général beaucoup plus long et beaucoup de messier.
Pour répondre à Josh commentaire - oui, je pense que le moyen le plus direct pour prouver l'équivalence est par l'intermédiaire de la FSA. Ce qui rend cette messier, c'est que la manière habituelle de construire un FSA est par l'intermédiaire d'un non-déterministe de la machine - son beaucoup plus facile d'exprimer u|v en tant que tout simplement la machine construite à partir de machines pour u et v avec un epsilon de transition pour les deux d'entre eux. Bien sûr, cela est équivalent à une machine déterministe, mais au risque de l'exponentielle de blow-up de l'état. Alors que la négation est beaucoup plus facile de le faire via une machine déterministe.
La preuve générale implique de prendre le produit cartésien de deux machines et de la sélection de ces états que vous souhaitez conserver à chaque point que vous souhaitez insérer un lookaround. L'exemple ci-dessus illustre ce que je veux dire, dans une certaine mesure.
Mes excuses pour ne pas fournir d'une construction.
MODIFIER:
J'ai trouvé un blog qui décrit un algorithme pour la génération d'une TFD d'une expression régulière augmentée avec lookarounds. Sa propre car l'auteur s'étend à l'idée d'une NFA-e avec "marqué epsilon-transitions" dans la manière évidente, puis explique comment convertir un tel automate dans un DFA.
J'ai pensé quelque chose comme cela serait une façon de le faire, mais je suis heureux que quelqu'un l'a écrit. Il était au-delà de moi, de venir avec quelque chose de si pur.
