331
\$\begingroup\$

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

\$\endgroup\$
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – breadbox May 30 '14 at 16:22
  • 9
    \$\begingroup\$ literals won't work because you're required to match the backslashes for example /aaa/ will match aaa but not /aaa/ \$\endgroup\$ – Dylan Madisetti May 30 '14 at 16:28
  • 2
    \$\begingroup\$ @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). \$\endgroup\$ – Martin Ender May 30 '14 at 19:18
  • 3
    \$\begingroup\$ 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" ;) \$\endgroup\$ – Paweł Tokarz May 30 '14 at 22:49
  • 3
    \$\begingroup\$ 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 /" \$\endgroup\$ – slebetman Jun 18 '14 at 2:44
582
+650
\$\begingroup\$

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:

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

Try it here.

Original version, 188 bytes

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

/^(?=.{173}\Q\2\)){2}.{11}$\E\/\z)((?=(.2.|))\2\/\2\^\2\(\2\?=\2\.\2\{173}\2\\Q\2\\2\2\\\2\)\2\)\2\{2}\2\.\2\{11}\2\$\2\\E\2\\\2\/\2\\z\2\)\2\(\2\(\2\?=\2\(\2\.2\2\.\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\/D\2\$\2\)\2\(\2\(\2\?=\2\(\2\.2\2\.\2\|\2\)\2\)){2}.{12}$/D

Try it here.

Expanded version:

/^(?=.{173}\Q\2\)){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\\Q\2\\2\2\\\2\)\2\)\2\{2}\2\.
   \2\{11}\2\$\2\\E\2\\\2\/\2\\z\2\)      # 1st line escaped.
   \2\(\2\(\2\?=\2\(\2\.2\2\.\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\.
  • \Q\2\)){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.

\$\endgroup\$
  • 5
    \$\begingroup\$ Impressive. I spent a while trying to get it to match something else, to no success. \$\endgroup\$ – primo Jun 16 '14 at 15:18
  • 73
    \$\begingroup\$ how (the hell) could an human produce such a thing? \$\endgroup\$ – xem Jun 16 '14 at 18:33
  • 60
    \$\begingroup\$ This deserves to be the highest voted answer on this site. \$\endgroup\$ – Cruncher Jun 16 '14 at 20:39
  • 43
    \$\begingroup\$ This is the most absurd, incredible thing I've ever seen. \$\endgroup\$ – Alex A. Jan 12 '16 at 19:09
  • 22
    \$\begingroup\$ Someone tweeted this post so I got 49 upvotes in a day... \$\endgroup\$ – jimmy23013 Nov 6 '16 at 8:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.