Закончены ли регулярные выражения .NET по Тьюрингу?

Question

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

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

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

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

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

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

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

Answer 1

В теории вычислений регулярное выражение описывает регулярный язык. Класс регулярных языков - это как раз те языки, которые могут распознаваться каким-либо конечным автоматом или генерироваться обычной грамматикой. Однако описанный вами пример (сбалансированные фразы) не является обычным языком и не может быть распознан конечным автоматом или сгенерирован обычной грамматикой. Фактически, это пример из учебника того, что называется контекстно-свободный язык . Для этого требуется автомат для распознавания. Класс контекстно-свободных языков является расширенным набором обычных языков, но является подходящим подмножеством для изучения законченных языков. Синтаксис (в отличие от семантики) большинства языков программирования является языком без контекста. Если вы хотите узнать больше об этой теме, вы можете начать с иерархии Хомского

Answer 2

Вы в значительной степени упускаете определение полного Тьюринга.

Полнота Тьюринга, названная в честь Алана Тьюринга, важна тем, что любой правдоподобный проект для вычислительного устройства, столь продвинутого до настоящего времени, может быть воспроизведен универсальнымМашина Тьюринга - наблюдение, которое стало известно как тезис Черча-Тьюринга.Таким образом, машина, которая может действовать как универсальная машина Тьюринга, может в принципе выполнять любые вычисления, на которые способен любой другой программируемый компьютер.Однако это не имеет ничего общего с усилиями, необходимыми для написания программы для машины, временем, которое может понадобиться машине для выполнения вычислений, или любыми способностями, которыми может обладать машина, которые не связаны с вычислениями.

Теперь, вы не можете делать определенные вещи в регулярных выражениях, поэтому язык не завершен.

Вы действительно должны использовать то же определение, что и все остальные, вы знаете.Ограниченное понимание должно привести к установлению истины.

Answer 3

Регулярные выражения в .NET не завершены по Тьюрингу, потому что они всегда останавливаются. Этого нельзя сказать о обычной машине Тьюринга.

Answer 4

@ Инуяша: На самом деле вы можете делать сложения с помощью регулярного выражения. Ну, по крайней мере, проверьте, правильно ли выполнены вычисления. Единственное, что вы должны передать входному выражению в странном порядке (вы не можете перевернуть строку (или проверить, если она перевернута) с помощью регулярного выражения).

Узор:

abc
def
---
ghi

=> cfi beh adg

Предположим, вы хотите добавить 1011 к 0110 в двоичном виде:

01011
00110
-----
10001


=> 101 110 010 100 001

Если вы передадите этот вход в порядке старших значащих битов, перемежая первый операнд, второй операнд и вывод, вы получите строку 101110010100001. Это может соответствовать

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

Который является регулярным выражением садового сорта. Вы могли бы расширить это до десятичного сложения, но регулярное выражение усложнилось бы.