> Is there a regular expression to detect a valid regular expression?

No, there is not. For example, parentheses in a regex must be balanced, and (famously) there is no regex to detect balanced parentheses.

More precisely, it is arbitrarily deep nested clauses that cannot be parsed, on account of true REs not being able to either use recursion or keep count of how deep they are.

https://blogs.msdn.microsoft.com/jaredpar/2008/10/15/regular...

Can regex engines actually process arbitrarily deep nestings themselves though?

It seems to me it would start getting computationally expensive very quickly to search for those kinds of regexes, so is 'arbitrarily deep' a practical concern for todays hardware?

Yes, regex engines that are designed to do so run in linear time on the size of the regex (as well as linear time with respect to the length of the input).

One such engine is rust's https://github.com/rust-lang/regex

It can process arbitrary deep nestings? I'm not familiar with it, but I had a look and I can't see anything in there that would allow it to do it. Can you point to syntax that allows it?

In general regex's that run in linear time are based on DFA's (as opposed to NFA's - which is what most use).

A DFA is part of the Chomsky hierarchy of languages that has DFA's at the bottom (aka regex's, least powerful - can't handle recursive structures), a DFA coupled with an infinite stack for memory (aka LR parsers, can't handle context sensitive grammars, also runs in very close to linear time), and finally a DFA coupled with an infinite tape (aka Turing Machine, can do any sort of computation).

In each of these cases the DFA (regex) is essentially a computer program and all they are doing is allowing it to store stuff on various kinds of memory (none, stack, tape with arbitrary movements). An interesting corollary of this is any computer program can be expressed as a DFA.