Регулярные выражения часто называют классическим примером языка, который не является полным. Например, «регулярные выражения» даются в качестве ответа на этот вопрос SO для поиска языков, не являющихся полными по Тьюрингу .
В моем, возможно, несколько базовом, понимании понятия полноты поворота, это означает, что регулярные выражения нельзя использовать для проверки «сбалансированных» шаблонов. Сбалансированное значение имеет такое же количество открывающих символов, что и закрывающих. Это связано с тем, что для этого потребуется какое-то состояние, позволяющее сопоставить открывающие и закрывающие символы.
Однако реализация регулярных выражений .NET вводит понятие сбалансированной группы ]. Эта конструкция предназначена для того, чтобы вы могли вернуться назад и посмотреть, совпала ли предыдущая группа. Это означает, что регулярные выражения .NET:
^(?a)*(?<-p>b)*(?(p)(?!))$
Могут соответствовать шаблону, который:
ab
aabb
aaabbb
aaaabbbb
... etc. ...
Означает ли это, что регулярные выражения .NET завершены по Тьюрингу? Или есть что-то еще, чего не хватает, чтобы язык был полным по Тьюрингу?