65
\$\begingroup\$

Your mission is to write the shortest valid regular expression that no string can match, empty string included.

Submissions must have this form ("literal notation"):

/pattern/optional-flags

Shortest regexp wins. The regexp size is counted in characters. (including slashes and flags)

Please explain how your regexp works (if it's not trivial)

Thanks, and have fun!

\$\endgroup\$
7
  • \$\begingroup\$ This inspired a question from me. I'm going to wait a few days though. Don't want 2 regex questions active at the same time \$\endgroup\$
    – Cruncher
    Jan 13 '14 at 21:31
  • 14
    \$\begingroup\$ "Valid" according to which implementation? I've just found an amusing one that Perl is okay with (and that is valid according to the only RE grammar I can find, but that grep and Python's re module refuse. \$\endgroup\$
    – jscs
    Jan 13 '14 at 22:24
  • 2
    \$\begingroup\$ Yes, which dialect(s) of regex? There are many many different ones. \$\endgroup\$ Jan 14 '14 at 4:53
  • 2
    \$\begingroup\$ But what about Presidents' names? xkcd.com/1313 \$\endgroup\$ Jan 14 '14 at 14:05
  • \$\begingroup\$ @CarlWitthoft You need to be a program to participate in that contest: codegolf.stackexchange.com/q/17718/2180 \$\endgroup\$
    – boothby
    Jan 14 '14 at 16:18

23 Answers 23

62
\$\begingroup\$

6 chars

Following on the answers of primo and Peter Taylor, and a hint from man perlre:

/(?!)/

This perl-compatible regex matches an empty string which is not followed by another empty string.

\$\endgroup\$
6
  • \$\begingroup\$ +1 - This is probably the shortest answer which is widely portable (along with /x\by/, but if I ever actually had to use a regex like this - for whatever reason - then this answer is also the clearest one) \$\endgroup\$ Jan 14 '14 at 17:06
  • \$\begingroup\$ @m.buettner: Thanks. primo's /(*FAIL)/ is probably clearer, though. (And actually man perlre gave it away by mentioning that mine actually expands to his internally.) \$\endgroup\$ Jan 14 '14 at 17:17
  • \$\begingroup\$ /(*FAIL)/ is not as portable though. And even in Perl, I think it's a more obscure feature than a negative lookahead. \$\endgroup\$ Jan 14 '14 at 17:20
  • 3
    \$\begingroup\$ You get lookarounds in almost all of the popular (Perl-inspired) flavours today, whereas I've never seen these control verbs anywhere but in Perl. \$\endgroup\$ Jan 14 '14 at 17:23
  • 1
    \$\begingroup\$ In fact, Perl documentation (and -Mre=debug) says that (?!) is optimized into (*FAIL) by Perl regex optimizer (OPFAIL according to -Mre=debug). Also, I don't think I saw (*FAIL) outside of Perl 5 (and Perl 6, where it's called <!>). \$\endgroup\$ Jan 14 '14 at 20:07
42
\$\begingroup\$

8 chars

/(?=a)b/

We require a string containing a character which is both a and b, which is obviously impossible.

\$\endgroup\$
5
  • 20
    \$\begingroup\$ /(?!x)x/ looks even more impossible ;-) \$\endgroup\$
    – Howard
    Jan 13 '14 at 17:58
  • \$\begingroup\$ @PeterTaylor where? \$\endgroup\$
    – o0'.
    Jan 14 '14 at 12:09
  • \$\begingroup\$ @Lohoris, where what? \$\endgroup\$ Jan 14 '14 at 12:12
  • \$\begingroup\$ @PeterTaylor where did he put those absurd rules you talk about, I couldn't find them. \$\endgroup\$
    – o0'.
    Jan 14 '14 at 12:13
  • 8
    \$\begingroup\$ guys, sorry for the counting i chose, i thought it would be simpler to include slashes because of the optional flags that could come after them. \$\endgroup\$
    – xem
    Jan 14 '14 at 17:03
34
\$\begingroup\$

5 chars

Unlike everybody who abuses $ and ^... this actually works in Perl:

/V\A/

\A matches the beginning of the string.

\$\endgroup\$
2
  • \$\begingroup\$ It works with ^ too. \$\endgroup\$
    – Tomas
    Feb 2 '14 at 14:30
  • \$\begingroup\$ Nice picket fence :) \$\endgroup\$
    – Wezl
    Mar 25 at 18:48
30
\$\begingroup\$

6 chars

/x\by/

Based on Sven Hohenstein's answer.

\$\endgroup\$
28
\$\begingroup\$

8 characters

/\w\b\w/

A word boundary (\b) surrounded by 'word' characters (\w - one of [_a-zA-Z0-9]). It is unmatchable since one of the characters preceding or following a word boundary must be a non-'word' character.

By the way: this is similar to the unmatchable expression

/\W\b\W/

where \W means non-'word' character.

\$\endgroup\$
3
  • \$\begingroup\$ This is 8 characters according to the rules of the competition, because the wrapping slashes / count. See OP's entry, for example. It's a great entry, though! \$\endgroup\$
    – jscs
    Jan 14 '14 at 1:41
  • \$\begingroup\$ It also might be a winner (or tied with Peter Taylor's entry), given the implementation-dependent problems with some of the shorter entries! \$\endgroup\$
    – jscs
    Jan 14 '14 at 2:03
  • \$\begingroup\$ Very elegant! I thought there must be something like this! \$\endgroup\$
    – Tomas
    Feb 2 '14 at 14:31
21
\$\begingroup\$

5 characters

/$.^/

/$^/ will match an empty string, whereas requiring a character in between will not.

\$\endgroup\$
6
  • 6
    \$\begingroup\$ This unfortunately matches "$a^" (or anything in place of the 'a') in Perl (and maybe sed). Still a nice one, though! \$\endgroup\$
    – jscs
    Jan 14 '14 at 2:00
  • \$\begingroup\$ @JoshCaswell: I guess perl might interpret $. as the current line number variable. Which might be empty, in which case this will be /^/. \$\endgroup\$
    – MvG
    Jan 14 '14 at 8:44
  • \$\begingroup\$ A character 'between' just means a one-character string. \$\endgroup\$
    – jwg
    Jan 14 '14 at 12:38
  • 3
    \$\begingroup\$ @jwg notice the swapped ^ and $ \$\endgroup\$
    – mniip
    Jan 14 '14 at 14:10
  • \$\begingroup\$ I tried the pattern '$^' with grep, but unfortunately it matched the string '$^'. Smartass grep. \$\endgroup\$ Jan 15 '14 at 15:07
20
\$\begingroup\$

4 chars

/$a/

searches a "a" after the end of the string.

or

/a^/

searches a before the beginning of the string.

\$\endgroup\$
9
  • 22
    \$\begingroup\$ Why post the question if you know that there's a two-char solution? \$\endgroup\$ Jan 13 '14 at 17:41
  • 4
    \$\begingroup\$ @Howard: That matches an empty string: jsfiddle.net/RjLxJ \$\endgroup\$
    – ProgramFOX
    Jan 13 '14 at 18:01
  • 10
    \$\begingroup\$ Why do I always find these problems after an unbeatable solution is provided :( \$\endgroup\$
    – Cruncher
    Jan 13 '14 at 21:23
  • 48
    \$\begingroup\$ -1: Putting ^ and $ in "illegal" positions just causes them to be treated as ordinary characters. Your first example matches the literal $a in sed and probably other programs. \$\endgroup\$ Jan 13 '14 at 23:02
  • 2
    \$\begingroup\$ @Ben Jackson, that's not true for POSIX EREs. Try echo 'a^b' | grep 'a^b' vs. echo 'a^b' | grep -E 'a^b'. Check out 9.4.9 ERE Expression Anchoring \$\endgroup\$
    – laindir
    Jan 14 '14 at 16:05
20
\$\begingroup\$

9 chars

I'm not sure but /[^\S\s]/ should be unmatchable since it means not any character, but at least one of them.

\$\endgroup\$
2
  • \$\begingroup\$ You don't need the +. \$\endgroup\$ Jan 13 '14 at 17:37
  • 10
    \$\begingroup\$ /[^\S\s]/ = 9 chars \$\endgroup\$
    – xem
    Jan 13 '14 at 17:38
19
\$\begingroup\$

4 characters

(ECMAScript flavour only)

/[]/

In other flavours this is not a valid character class (the ] would be considered a character in the class, so the expression isn't valid, because the class is never closed), but the ECMAScript standard accepts empty character classes. Since it is a class it has to match a character (so empty strings don't match), but since not a single character is included no actual character will match either.

\$\endgroup\$
4
  • \$\begingroup\$ Wouldn't this match an empty string even though you says it has to match a character? Or do you think this is illegal: /[]{0}/. (Ps. though my own answer partially looks like yours, I actually read yours after writing mine.) \$\endgroup\$
    – nl-x
    Jan 14 '14 at 11:46
  • \$\begingroup\$ @nl-x paste this into your browser's console: /[]/.test(""). it returns false. a character class can never match an empty string, even if it doesn't contain characters (I imagine they are implemented like "IF the next character in the string is one of those listed, match; ELSE fail"). /[]{0}/ is legal (in ECMAScript) and does match the empty string... however, I'm not sure how that is relevant to my answer. \$\endgroup\$ Jan 14 '14 at 16:12
  • \$\begingroup\$ Fails in Ruby 2.0 \$\endgroup\$
    – Nakilon
    Jan 14 '14 at 19:01
  • 1
    \$\begingroup\$ @Nakilon of course it does. Ruby doesn't implement the ECMAScript flavour. \$\endgroup\$ Jan 14 '14 at 19:45
19
\$\begingroup\$

6 characters

/\b\B/

This matches a word boundary (\b) that isn't a word boundary (\B), which is obviously impossible.

\$\endgroup\$
3
  • \$\begingroup\$ doesn't this one search for a word-boundary followed by a non-word-boundary? \$\endgroup\$
    – grexter89
    Jan 14 '14 at 14:16
  • 1
    \$\begingroup\$ @grexter89 Yes, but they can't have any characters in between. i.e. The boundary and the non-boundary have to occupy the same space. \$\endgroup\$ Jan 14 '14 at 14:17
  • 2
    \$\begingroup\$ I like this one. Good catch. \$\endgroup\$
    – primo
    Jan 14 '14 at 14:33
16
\$\begingroup\$

6 chars

/b++b/

Possessive quantifier looks for as many b's as possible, then 1 more. 6 chars but points for symmetry?

\$\endgroup\$
1
  • \$\begingroup\$ Huh... I just learned a new feature. Apparently, my regex skills are badly out of date. Thanks, and +1. \$\endgroup\$ Feb 2 '14 at 12:45
9
\$\begingroup\$

6 characters

/(\1)/

Not a winner, but I thought it was fun. grep and Python both barf on this one, but Perl seems okay with it.

Seems to be very implementation-dependent (which is hardly surprising, given its weirdness). Bob reports below that it matches anything in JavaScript's regex engine.

\$\endgroup\$
2
  • \$\begingroup\$ .NET's regex engine seems to accept it. \$\endgroup\$
    – Bob
    Jan 14 '14 at 1:45
  • \$\begingroup\$ And it always matches (an empty string) no matter what input on JS \$\endgroup\$
    – Bob
    Jan 14 '14 at 1:54
9
\$\begingroup\$

Maybe a bit of cheating, but…

\0

… is unmatchable in POSIX regex in virtually all, if not all, implementations. BASIC RE and EXTENDED RE, even.

And POSIX RE does not need those pesky slashes and flags PCRE has.

\$\endgroup\$
2
  • \$\begingroup\$ +1 Good!! Unfortunatelly, sole 0 doesn't work in PERL. "0"=~0 is true... \$\endgroup\$
    – Tomas
    Feb 2 '14 at 14:27
  • \$\begingroup\$ sole \0 ITYM? Yes, most perlre(1) and PCRE implementations do not use C strings but size-bounded buffers, in whom this trick will not work, but most POSIX RE implementations work on C strings. \$\endgroup\$
    – mirabilos
    Feb 3 '14 at 13:16
6
\$\begingroup\$

4 char:

/.^/

Works with GNU grep 2.5.1 and egrep.

\$\endgroup\$
5
  • \$\begingroup\$ /.^/ = 4 chars. \$\endgroup\$ Jan 14 '14 at 19:41
  • \$\begingroup\$ Why do you need the //? those are not required everywhere ;-) \$\endgroup\$
    – RSFalcon7
    Jan 14 '14 at 19:44
  • \$\begingroup\$ The wrapping slashes / count, see the original question ("including slashes and flags") and the OP's entry. \$\endgroup\$ Jan 14 '14 at 19:48
  • \$\begingroup\$ right! I miss read :( \$\endgroup\$
    – RSFalcon7
    Jan 14 '14 at 19:49
  • \$\begingroup\$ No, for the same reason as the one below: Actually, “^” is only special if at the beginning of the pattern. Any “^” after anything else does not need to be escaped, so this answer is wrong. \$\endgroup\$
    – mirabilos
    Dec 30 '14 at 15:38
5
\$\begingroup\$

5 chars

/^.^/

Matches string that begin with any single character before string begin.

\$\endgroup\$
6
  • 7
    \$\begingroup\$ Also matches the string ".^" \$\endgroup\$
    – boothby
    Jan 14 '14 at 4:57
  • \$\begingroup\$ @boothby: in which language does matches? in Python doesn't. re.findall(r'^.^', '.^', re.DEBUG) \$\endgroup\$ Jan 14 '14 at 8:39
  • 9
    \$\begingroup\$ +1 for using the manga operator (see stackoverflow.com/questions/3618340/…) \$\endgroup\$
    – prototype
    Jan 14 '14 at 19:11
  • 2
    \$\begingroup\$ It's broken in Perl. This question really should have set some ground rules about language. \$\endgroup\$
    – boothby
    Jan 14 '14 at 19:28
  • 1
    \$\begingroup\$ Actually, “^” is only special if at the beginning of the string. Any “^” after anything else does not need to be escaped, so this answer is wrong. \$\endgroup\$
    – mirabilos
    Oct 20 '14 at 12:54
5
\$\begingroup\$

Perl 6 (5 characters)

/<!>/

Sorta rule abuse (because Perl 6 regexes are different, and incompatible with stardard regexes by design), but I don't care. <!> rule informs Perl 6 that the regex doesn't match.

\$\endgroup\$
5
\$\begingroup\$

6 bytes

/(*F)/

An abbreviation for (*FAIL), supported by perl-compatable regex engines. Thanks to @HamZa for pointing this out.

9 bytes

/(*FAIL)/

Should work with any regex engine that supports verbs at all. I'm not convinced this really needs to be golfed any further.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ How does this work? \$\endgroup\$
    – boothby
    Jan 14 '14 at 5:49
  • \$\begingroup\$ @boothby (*FAIL) is a verb that always fails. \$\endgroup\$
    – primo
    Jan 14 '14 at 6:05
  • \$\begingroup\$ @primo you might just use /(*F)/ :) \$\endgroup\$
    – HamZa
    Jan 14 '14 at 19:01
3
\$\begingroup\$

4 chars with slashes 2 without

In the TXR language's regex engine, an empty character class [] matches no character, and therefore no string. It behaves this way because the character class requires a character match, and when it is empty it specifies that no character can satisfy it.

Another way is to invert the "set of all strings including empty" regex /.*/ using the complement operator: /~.*/. The complement of that set contains no strings at all, and so cannot match anything.

This is all documented in the man page:

   nomatch
          The  nomatch  regular  expression  represents  the empty set: it
          matches no strings at all, not even the empty string.  There  is
          no  dedicated  syntax  to  directly express nomatch in the regex
          language.  However, the empty character class []  is  equivalent
          to nomatch, and may be considered to be a notation for it. Other
          representations of nomatch are possible: for instance, the regex
          ~.* which is the complement of the regex that denotes the set of
          all possible strings, and thus denotes the empty set. A  nomatch
          has  uses;  for instance, it can be used to temporarily "comment
          out" regular expressions. The regex ([]abc|xyz) is equivalent to
          (xyz), since the []abc branch cannot match anything. Using [] to
          "block" a subexpression allows you to leave it  in  place,  then
          enable it later by removing the "block".

The slashes are not part of the regex syntax per se; they are just punctuation which delimits regexes in the S-expression notation. Witness:

# match line of input with x variable, and then parse that as a regex
#
$ txr -c '@x
@(do (print (regex-parse x)) (put-char #\newline))' -
ab.*c                               <- input from tty: no slashes.
(compound #\a #\b (0+ wild) #\c)    <- output: AST of regex
\$\endgroup\$
1
  • \$\begingroup\$ thanks for your answer and sorry again for the slash-counting. I thought it would be easier to include them if people used flags. \$\endgroup\$
    – xem
    Jan 15 '14 at 7:18
3
\$\begingroup\$

4 chars

/$./

Needs any character after the string ends

\$\endgroup\$
1
  • \$\begingroup\$ Similarily to the other two ones, $ is only special at the end of the pattern. \$\endgroup\$
    – mirabilos
    Dec 30 '14 at 15:39
1
\$\begingroup\$

6 chars

(or 4, depending on how you look at it)

/{,0}/
\$\endgroup\$
3
  • \$\begingroup\$ Fails in Ruby 2.0 \$\endgroup\$
    – Nakilon
    Jan 14 '14 at 19:02
  • \$\begingroup\$ In which regex implementations does this not give an error? \$\endgroup\$ Jan 15 '14 at 9:43
  • \$\begingroup\$ I only tested it using PHP's preg_match. \$\endgroup\$
    – Tercy
    Jan 15 '14 at 13:12
1
\$\begingroup\$

This is a 5 char regex.

/[]+/

It matches an empty group 1 or more times.

EDIT:

Removed my answer for other flavours:

/.{-1}/

Anything that is not a number inside {} will match the text.

This one will match ".{-1}"

\$\endgroup\$
3
  • \$\begingroup\$ Note that this only works in the ECMAScript flavour. In most (all?) others it is not a valid expression. \$\endgroup\$ Jan 14 '14 at 16:14
  • \$\begingroup\$ Isn't it invalid? \$\endgroup\$
    – Wasi
    Jan 14 '14 at 16:14
  • \$\begingroup\$ @Wasi not in ECMAScript-conforming flavours \$\endgroup\$ Jan 14 '14 at 16:17
0
\$\begingroup\$

5 characters

Hope this doesnt sound stupid: /[]+/

\$\endgroup\$
2
  • \$\begingroup\$ Nope. Not a valid regex. \$\endgroup\$ Jan 14 '14 at 13:59
  • \$\begingroup\$ @RyanCarlson It is valid and legal... At least in Ecmascript. \$\endgroup\$
    – nl-x
    Jan 15 '14 at 6:49
-3
\$\begingroup\$
/$^/

A thing that ends before it has begun...

\$\endgroup\$
10
  • 7
    \$\begingroup\$ Matches the empty string (in some RE implementations, anyways). \$\endgroup\$
    – jscs
    Jan 13 '14 at 22:37
  • 1
    \$\begingroup\$ Your implementation is broken :) \$\endgroup\$
    – simon
    Jan 13 '14 at 22:39
  • 2
    \$\begingroup\$ Better let Guido know. \$\endgroup\$
    – jscs
    Jan 13 '14 at 22:45
  • 7
    \$\begingroup\$ More importantly, as Ben Jackson pointed out, in Perl, where it doesn't match "", it does match a string containing those two literal characters: "$^". \$\endgroup\$
    – jscs
    Jan 14 '14 at 1:44
  • \$\begingroup\$ +1 I just wanted to post the same! @Josh, it does work in PERL, and it doesn't match empty string! Ben's comment is broken, I replied to it. \$\endgroup\$
    – Tomas
    Feb 2 '14 at 14:14

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.