Les expressions régulières de .NET complète Turing?

Question

Les expressions régulières sont souvent dénoncées comme l'exemple classique d'une langue qui ne tourne pas complète. Par exemple « expressions régulières » est donnée en tant que réponse à cette question SO à la recherche pour les langues qui ne sont pas Türing complète .

Dans mon, peut-être un peu de base, la compréhension de la notion de Turning exhaustivité, cela signifie que les expressions régulières ne peut pas être utilisé pour vérifier les modèles qui sont « équilibrés ». sens équilibré ont un nombre égal de caractères comme l'ouverture des caractères de clôture. En effet, pour ce faire, il faudrait vous d'avoir une sorte d'état, pour vous permettre de faire correspondre l'ouverture et la fermeture des caractères.

Cependant, la mise en œuvre .NET des expressions régulières introduit la notion d'un groupe équilibré . Cette construction est conçu pour vous permettre de revenir en arrière et voir si un groupe précédent a été adapté. Cela signifie qu'une des expressions régulières .NET:

^(?<p>a)*(?<-p>b)*(?(p)(?!))$

pourrait correspondre à un modèle que:

ab
aabb
aaabbb
aaaabbbb
... etc. ...

Est-ce que les expressions régulières de ce moyen .NET sont complets Turing? Ou y at-il d'autres choses qui manquent qui seraient nécessaires pour que la langue soit complète Turing?

Answer 1

Dans la théorie de calcul, une expression régulière décrit un langage régulier. La classe des langages réguliers est précisément ces langues qui peuvent être reconnues par une machine à états finis ou générés par une grammaire régulière. Cependant, l'exemple que vous avez décrit (phrases équilibrées) ne sont pas une langue régulière et ne peut pas être reconnu par une machine à états finis ou généré par une grammaire régulière. En fait, ce manuel un exemple de ce qu'on appelle un langue sans contexte . Ceux-ci ont besoin d'un automate de poussée vers le bas pour la reconnaissance. La classe des langues sans contexte est un ensemble des langues ordinaires, mais un sous-ensemble de turing langues complètes. La syntaxe (par opposition à la sémantique) de la plupart des langages de programmation est un langage hors-contexte. Si vous êtes intéressé à en apprendre davantage sur ce sujet, vous pouvez commencer par le hiérarchie Chomsky

Answer 2

Vous manquez à peu près la définition de turing complète.

Turing-complet, nommé d'après Alan Turing, est significative que chaque conception plausible pour une informatique dispositif jusqu'à présent avancé peut être émulé par une machine de Turing universelle - un observation qui est devenu connu sous le nom la thèse Church-Turing. Ainsi, un machine qui peut agir comme un universel Turing machine peut, en principe, effectuer un calcul que tout autre ordinateur programmable est capable. Cependant, cela n'a rien à voir avec l'effort requis pour écrire un programme pour la machine, le temps peut prendre pour la machine pour effectuer le calcul, ou toutes les capacités des machine peut posséder sans rapport au calcul.

Maintenant, vous ne pouvez pas faire certaines choses dans les expressions régulières, de sorte que le langauge ne Türing complète.

Il faut vraiment utiliser la même définition comme tout le monde, vous savez. compréhension limitée devrait déclencher de trouver la vérité.

Answer 3

Regex de .NET ne sont pas complète parce qu'ils Turing arrêtent toujours. Cela ne peut pas dire d'une machine de Turing générale.

Answer 4

@Inuyasha: En fait, vous pouvez faire plus avec une expression régulière. Eh bien au moins vérifier si le calcul est effectué correctement. La seule chose est que vous devez donner l'entrée à l'expression rationnelle dans un ordre étrange (vous ne pouvez pas inverser une chaîne (ou vérifier si elle est inversée) avec une expression régulière).

Le motif est:

abc
def
---
ghi

=> cfi beh adg

Supposons que vous voulez ajouter un 1011 0110 en binaire:

01011
00110
-----
10001


=> 101 110 010 100 001

Si vous donnez cette entrée dans l'ordre de location bits significatifs à la plus grande, intercalant le premier opérande, deuxième opérande, et la sortie, vous obtiendrez la chaîne 101110010100001. Cela peut aller de pair avec

((000|011|101)|(110(010|100|111)*001))*

Ce qui est une expression régulière variété de jardin. Vous pouvez étendre cette addition décimale, mais la regex devenir fou compliqué.