What's a Regular Expression DoS?

What is a regular expression Denial of Service and how do we protect against it? Let's investigate and discover how innocuous regex can take down our servers.