Регулярные выражения .NET Turing завершены?

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

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

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

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

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

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

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

Ответ 1

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

Ответ 2

Вы в значительной степени пропустите определение завершения turing.

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

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

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

Ответ 3

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

Образец:

abc
def
---
ghi

=> cfi beh adg

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

01011
00110
-----
10001


=> 101 110 010 100 001

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

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

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

Ответ 4

Regex в .NET не является полным Turing, потому что они всегда останавливаются. Это нельзя сказать об общей машине для turing.