Are Perge regexes turing complete?

Question

I have seen Ruby and Perl programmers complete some complex code problems with regular expressions. The capabilities of lookahead and lookbehind in Perl regular expressions make them more powerful than regular expression implementations in most other languages. I was wondering how strong they really are.

Is there an easy way to prove or disprove that Perl Turing regular expressions are complete ?

Answer 1

With the exception of any inline code, such as ?{ } , They probably do not cover all context-free, and especially Turing Machines. They can, but as far as I know, no one has proven it anyway. Given that people have been trying for some time to solve some context-related issues with Perl regular expressions and have not yet come up with a solution, it is likely that they are not context-sensitive.

There is an interesting discussion about which features are just convenient, and which actually add strength. For example, matching 0 ⁿ * 1 * 0 ⁿ (this is a notation for "any number of zeros followed by one followed by the same number of zeros as before") is not something that can be done with pure regular expressions . You can prove that this cannot be done with regular expressions using the pump lemma, but a simple, informal proof is that the regular expression should count an arbitrary number of zeros, and regular expressions cannot count.

However, backlinks may correspond to those:

 /(0*) 1 \1/x; 

So, this means that backlinks give you more energy and more than convenience. What else can give us more strength, interesting?

In addition, Perl6 “patterns” (they don’t even pretend that they are regular expressions) are designed to look like Perl5 regexes (so you don’t have to retrain a lot), but they have enough additional functions that are completely contextual free. They are actually designed so that you can use them to change the way you analyze in the lexical field.

Answer 2

There are at least two discussions: completeness and Turing regular expressions and Are Perl patterns universal? with further links.

The consensus (to my unprepared eye) seems like the answer is no, but I'm not sure if I understand everything correctly.

Answer 3

There are two cases for regular expressions in Perl:

• With embedded code: they certainly complete Turing.
• Without inline code: they always stop, so they are not shared Turing machines.

Every ordinary language can be adopted by a state machine . Its input should be the final line.

[...] a deterministic finite state machine (DFA), also known as a deterministic finite state machine, is a finite state machine that accepts / rejects finite strings of characters [...].

The same applies to Turing machines : a formal definition does not even have an input. It must be encoded in a finite number of states.

Alternative (equivalent) definitions include input, but it must be finite.