Regex that only matches itself

Question

There are some pretty cool challenges out there involving regex (Self-matching regex, Regex validating regex)

This may well be impossible, but is there a regex that will ONLY match itself?

NOTE, delimiters must be included:

for example /thing/ must match /thing/ and not thing. The only match possible for your expression must be the expression itself. Many languages allow the implementation of a string in the place of a regular expression. For instance in Go

package main
import "fmt"
import "regexp"
func main() {
 var foo = regexp.MustCompile("bar")
 fmt.Println(foo.MatchString("foobar"))
}

but for the sake of the challenge, let the expression be delimited (starting symbol, expression, ending symbol ex: /fancypantpattern/ or @[^2048]@), if you want to argue quotes as your delimiter, so be it. I think given the apparent difficulty of this problem it won't make much of a difference.

To help you along:

Quick hack I put together for rubular.com (a webpage for ruby regex editing):

var test = document.getElementById("test")
,regex = document.getElementById("regex")
,delimiter="/"
,options = document.getElementById("options")
,delay = function(){test.value = delimiter + regex.value + delimiter + options.value}
,update = function(e){
 // without delay value = not updated value
 window.setTimeout(delay,0);
}
regex.onkeydown = update;
options.onkeydown = update;

Even though this is technically 'code golf' I will be very impressed if anyone can find an answer/ prove it is impossible.

Link is now fixed. Sorry to all

Winning answer thus far: jimmy23013 with 40 characters

• breadbox: Obviously any regular expression that only includes literals will work: //, /a/, /xyz/, etc. It might be good to require that the regex has to include a non-literal operation.
• Dylan Madisetti: literals won't work because you're required to match the backslashes for example /aaa/ will match aaa but not /aaa/
• Martin Ender: @DylanMadisetti Do we have to use // delimiters, or can we choose other delimiters (PCRE supports pretty much any character, and in particular you can use matched parentheses/braces/brackets as delimiters).
• Paweł Tokarz: I think that this is quite nice mathematical/computational problem and the proof might be not easy... Many important theorems started as just a simple question to play with, so maybe in 5 years there will be wikipedia article "Madisetti problem" ;)
• slebetman: Yes, exactly. In some languages (think grep in bash) the delimiter is essentially an empty string. So assuming that regexp requires delimiters is already wrong in the first place. Indeed, since grep is one of the earliest implementation of regexp the canonical definition of regexp don't have delimiters. The wrongest manifestation of this assumption is PHP which requires two delimiters: "/ and /"

Answer 1

PCRE flavor, (削除) 261 (削除ここまで) (削除) 289 (削除ここまで) (削除) 210 (削除ここまで) (削除) 184 (削除ここまで) (削除) 127 (削除ここまで) (削除) 109 (削除ここまで) (削除) 71 (削除ここまで) (削除) 53 (削除ここまで) (削除) 51 (削除ここまで) (削除) 44 (削除ここまで) 40 bytes

Yes, it is possible!

<^<()(?R){2}>\z|1円\Q^<()(?R){2}>\z|1円\Q>

Try it here. (But / is shown to be the delimiter on Regex101.)

^{Please refrain from making unnecessary edits (updates) on the Regex101 page. If your edit doesn't actually involve improving, trying or testing this regex, you could fork it or create new ones from their homepage.}

The version works more correctly on Regex101 (44 bytes):

/^\/()(?R){2}\/\z|1円\Q^\/()(?R){2}\/\z|1円\Q/

Try it here.

This is much simpler than the original version and works more like a traditional quine. It tries to define a string without using it, and use it in a different place. So it can be placed very close to one end of the regex, to reduce the number of characters needing more characters to define the matching pattern and repeated more times.

Explanations:

• \Q^\/()(?R){2}\/\z|1円\Q matches the string ^\/()(?R){2}\/\z|1円\Q. This uses a quirk that \Q...\E doesn't have to be closed, and unescaped delimiters work in \Q. This made some previous versions work only on Regex101 and not locally. But fortunately the latest version worked, and I golfed off some more bytes using this.
• 1円 before the \Q matches the captured group 1. Because group 1 doesn't exist in this option, it can only match in recursive calls. In recursive calls it matches empty strings.
• (?R){2} calls the whole regex recursively twice, which matches ^\/()(?R){2}\/\z|1円\Q for each time.
• () does nothing but capture an empty string into group 1, which enables the other option in recursive calls.
• ^\/()(?R){2}\/\z matches (?R){2} with delimiters added, from the beginning to the end. The \/ before the recursive calls also made sure this option itself doesn't match in recursive calls, because it won't be at the beginning of the string.

51 bytes with closed \Q...\E:

/\QE1円|^\/(\\)Q(?R){2}z\/\E1円|^\/(\\)Q(?R){2}z\/\z/

Try it here.

Original version, 188 bytes

Thanks to Martin Büttner for golfing off about 100 bytes!

/^(?=.{173}\Q2円\)){2}.{11}$\E\/\z)((?=(.2.|))2円\/2円\^2円\(2円\?=2円\.2円\{173}2円\\Q2円\2円2円\\2円\)2円\)2円\{2}2円\.2円\{11}2円\$2円\\E2円\\2円\/2円\\z2円\)2円\(2円\(2円\?=2円\(2円\.22円\.2円\|2円\)2円\)){2}.{11}$/

Try it here.

Or 210 bytes without \Q...\E:

/^(?=.{194}\2円\\.\)\{2}\.\{12}\$\/D$)((?=(.2.|))2円\/2円\^2円\(2円\?=2円\.2円\{194}2円\\2円\2円2円\\2円\\2円\.2円\\2円\)2円\\2円\{2}2円\\2円\.2円\\2円\{12}2円\\2円\$2円\\2円\/D2円\$2円\)2円\(2円\(2円\?=2円\(2円\.22円\.2円\|2円\)2円\)){2}.{12}$/D

Try it here.

Expanded version:

/^(?=.{173}\Q2円\)){2}.{11}$\E\/\z) # Match things near the end.
((?=(.2.|)) # Capture an empty string or 2円\ into group 2.
 2円\/2円\^2円\(2円\?=2円\.2円\{173}2円\\Q2円\2円2円\\2円\)2円\)2円\{2}2円\.
 2円\{11}2円\$2円\\E2円\\2円\/2円\\z2円\) # 1st line escaped.
 2円\(2円\(2円\?=2円\(2円\.22円\.2円\|2円\)2円\) # 2nd line escaped.
){2}
.{11}$/x

(削除) Extensions like (?= and 1円 have made the so-called "regular" expressions no longer regular, which also makes quines possible. (削除ここまで) Backreference is not regular, but lookahead is.

Explanation:

• I use 2円\ in place of \ to escape special characters. If 2円 matches the empty string, 2円\x (where x is a special character) matches the x itself. If 2円 matches 2円\, 2円\x matches the escaped one. 2円 in the two matches of group 1 can be different in regex. In the first time 2円 should match the empty string, and the second time 2円\.
• \Q2円\)){2}.{11}$\E\/\z (line 1) matches 15 characters from the end. And .{11}$ (line 7) matches 11 characters from the end (or before a trailing newline). So the pattern just before the second pattern must match the first 4 or 3 characters in the first pattern, so 2円\.2円\|2円\)2円\) must match ...2円\) or ...2円\. There cannot be a trailing newline because the last character should be ). And the matched text doesn't contain another ) before the rightmost one, so all other characters must be in the 2円. 2円 is defined as (.2.|), so it can only be 2円\.
• The first line makes the whole expression matches exactly 188 characters since everything has a fixed length. The two times of group 1 matches 45*2 characters plus 29 times 2円. And things after group 1 matches 11 characters. So the total length of the two times 2円 must be exactly 3 characters. Knowing 2円 for the second time is 3 characters long, it must be empty for the first time.
• Everything except the lookahead and 2円 are literals in group 1. With the two times 2円 known, and the last few characters known from the first line, this regex matches exactly one string.
• Martin Büttner comes up with the idea of using lookahead to capture group 2 and make it overlap with the quine part. This removed the characters not escaped in the normal way between the two times of group 1, and help avoided the pattern to match them in my original version, and simplified the regex a lot.

Regex without recursions or backreferences, 85 bytes

Someone may argue that expressions with recursions or backreferences are not real "regular" expressions. But expressions with only lookahead can still only match regular languages, although they may be much longer if expressed by traditional regular expressions.

/(?=.*(\QE\\){2}z\/\z)^\/\(\?\=\.\*\(\\Q.{76}\E\\){2}z\/\z)^\/\(\?\=\.\*\(\\Q.{76}\z/

Try it here.

610 bytes without \Q...\E (to be golfed):

/^(?=.{610}$)(?=.{71}(\(\.\{8\}\)\?\\.[^(]*){57}\)\{2\}\.\{12\}\$\/D$)((.{8})?\/(.{8})?\^(.{8})?\((.{8})?\?=(.{8})?\.(.{8})?\{610(.{8})?\}(.{8})?\$(.{8})?\)(.{8})?\((.{8})?\?=(.{8})?\.(.{8})?\{71(.{8})?\}(.{8})?\((.{8})?\\(.{8})?\((.{8})?\\(.{8})?\.(.{8})?\\(.{8})?\{8(.{8})?\\(.{8})?\}(.{8})?\\(.{8})?\)(.{8})?\\(.{8})?\?(.{8})?\\(.{8})?\\(.{8})?\.(.{8})?\[(.{8})?\^(.{8})?\((.{8})?\](.{8})?\*(.{8})?\)(.{8})?\{57(.{8})?\}(.{8})?\\(.{8})?\)(.{8})?\\(.{8})?\{2(.{8})?\\(.{8})?\}(.{8})?\\(.{8})?\.(.{8})?\\(.{8})?\{12(.{8})?\\(.{8})?\}(.{8})?\\(.{8})?\$(.{8})?\\(.{8})?\/D(.{8})?\$(.{8})?\)(.{8})?\(){2}.{12}$/D

Try it here.

The idea is similar.

/^(?=.{610}$)(?=.{71}(\(\.\{8\}\)\?\\.[^(]*){57}\)\{2\}\.\{12\}\$\/D$)
((.{8})?\/(.{8})?\^(.{8})?\((.{8})?\?=(.{8})?\.(.{8})?\{610(.{8})?\}(.{8})?\$(.{8})?\)
(.{8})?\((.{8})?\?=(.{8})?\.(.{8})?\{71(.{8})?\}
 (.{8})?\((.{8})?\\(.{8})?\((.{8})?\\(.{8})?\.(.{8})?\\(.{8})?\{8(.{8})?\\(.{8})?\}
 (.{8})?\\(.{8})?\)(.{8})?\\(.{8})?\?(.{8})?\\(.{8})?\\
 (.{8})?\.(.{8})?\[(.{8})?\^(.{8})?\((.{8})?\](.{8})?\*(.{8})?\)(.{8})?\{57(.{8})?\}
 (.{8})?\\(.{8})?\)(.{8})?\\(.{8})?\{2(.{8})?\\(.{8})?\}
 (.{8})?\\(.{8})?\.(.{8})?\\(.{8})?\{12(.{8})?\\(.{8})?\}
 (.{8})?\\(.{8})?\$(.{8})?\\(.{8})?\/D(.{8})?\$(.{8})?\)(.{8})?\(){2}.{12}$/D

The basic regular expression

If lookahead is not allowed, the best I can do now is:

/\\(\\\(\\\\){2}/

which matches

\\(\\\(\\

If {m,n} quantifier is not allowed, it is impossible because nothing which can only match one string, can match a string longer than itself. Of course one can still invent something like \q which only matches /\q/, and still say expressions with that regular. But apparently nothing like this is supported by major implementations.

• xem: how (the hell) could an human produce such a thing?
• Cruncher: This deserves to be the highest voted answer on this site.
• Alex A.: This is the most absurd, incredible thing I've ever seen.
• jimmy23013: Someone tweeted this post so I got 49 upvotes in a day...
• Kristopher Ives: Hats off to you you crazy regex bastard