Обычные ли .NET Выражения Turing complete?

Регулярные выражения часто называют классическим примером языка, который не является полным. Например, «регулярные выражения» даются в качестве ответа на этот вопрос SO для поиска языков, не являющихся полными по Тьюрингу .

В моем, возможно, несколько базовом, понимании понятия полноты поворота, это означает, что регулярные выражения нельзя использовать для проверки «сбалансированных» шаблонов. Сбалансированное значение имеет такое же количество открывающих символов, что и закрывающих. Это связано с тем, что для этого потребуется какое-то состояние, позволяющее сопоставить открывающие и закрывающие символы.

Однако реализация регулярных выражений .NET вводит понятие сбалансированной группы ]. Эта конструкция предназначена для того, чтобы вы могли вернуться назад и посмотреть, совпала ли предыдущая группа. Это означает, что регулярные выражения .NET:

^(?

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

Могут соответствовать шаблону, который:

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

Означает ли это, что регулярные выражения .NET завершены по Тьюрингу? Или есть что-то еще, чего не хватает, чтобы язык был полным по Тьюрингу?

11
задан Community 23 May 2017 в 11:45
поделиться