Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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!

share|improve this question
    
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 –  Cruncher Jan 13 at 21:31
11  
"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. –  Josh Caswell Jan 13 at 22:24
1  
Yes, which dialect(s) of regex? There are many many different ones. –  hippietrail Jan 14 at 4:53
1  
But what about Presidents' names? xkcd.com/1313 –  Carl Witthoft Jan 14 at 14:05
    
@CarlWitthoft You need to be a program to participate in that contest: codegolf.stackexchange.com/q/17718/2180 –  boothby Jan 14 at 16:18

24 Answers 24

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.

share|improve this answer
    
+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) –  Martin Büttner Jan 14 at 17:06
    
@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.) –  Nate Eldredge Jan 14 at 17:17
3  
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. –  Martin Büttner Jan 14 at 17:23
1  
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 <!>). –  xfix Jan 14 at 20:07
3  
Okay, nobody upvote this anymore. At 42 votes, it is the answer. –  The Guy with The Hat Jan 17 at 17:57

8 chars

/(?=a)b/

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

share|improve this answer
16  
/(?!x)x/ looks even more impossible ;-) –  Howard Jan 13 at 17:58
    
@PeterTaylor where? –  Lohoris Jan 14 at 12:09
    
@Lohoris, where what? –  Peter Taylor Jan 14 at 12:12
    
@PeterTaylor where did he put those absurd rules you talk about, I couldn't find them. –  Lohoris Jan 14 at 12:13
6  
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. –  xem Jan 14 at 17:03

5 chars

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

/V\A/

\A matches the beginning of the string.

share|improve this answer
    
It works with ^ too. –  Tomas Feb 2 at 14:30

6 chars

/x\by/

Based on Sven Hohenstein's answer.

share|improve this answer

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.

share|improve this answer
    
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! –  Josh Caswell Jan 14 at 1:41
    
It also might be a winner (or tied with Peter Taylor's entry), given the implementation-dependent problems with some of the shorter entries! –  Josh Caswell Jan 14 at 2:03
    
Very elegant! I thought there must be something like this! –  Tomas Feb 2 at 14:31

5 characters

/$.^/

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

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

4 chars

/$a/

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

or

/a^/

searches a before the beginning of the string.

share|improve this answer
17  
Why post the question if you know that there's a two-char solution? –  Peter Taylor Jan 13 at 17:41
3  
@Howard: That matches an empty string: jsfiddle.net/RjLxJ –  ProgramFOX Jan 13 at 18:01
9  
Why do I always find these problems after an unbeatable solution is provided :( –  Cruncher Jan 13 at 21:23
38  
-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. –  Ben Jackson Jan 13 at 23:02
1  
@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 –  laindir Jan 14 at 16:05

6 characters

I think this regex I made will work:

/\b\B/

It matches a word boundary (\b) that isn't a word boundary (\B). Which is impos—do I really have to explain this to you?

This is with my best understanding of regex. If I am wrong, please tell me. Anything contained in, not contained in, assumed to be implied by, warranted by, excluded from being warranted by, or vaguely alluded to in this document, or any other document resembling or not resembling this document in any way, shall not be attributed to, blamed upon, or otherwise associated with the named author, any alleged author, the sender, any of the sender's friends, enemies, or acquaintances, or the United States Government, or any other government of any city, county, state, province, or country, nor shall any of the aforementioned parties be held responsible, irresponsible, accountable, uncountable, or in any way involved with the aforementioned document or the presence or absence thereof.This does not reflect the thoughts or opinions of either myself, my company, my friends; don't quote me on that; don't quote me on anything; all rights reserved; distribution copyrighted to the extent that you may distribute this and all its associated parts freely but you may not make a profit from it or include this in commercial publications without written permission from the President; other copyright laws for specific items apply wherever noted; subject to change without notice; slightly enlarged to show detail; any resemblance to actual persons, living or dead, is unintentional and purely coincidental; hand wash only, tumble dry on low heat; do not bend, fold, mutilate, or spindle; your mileage may vary; accept no substitutes; for a limited time only; this offer is void where prohibited, taxed, or otherwise restricted; provided "as is" without any warranties expressed or implied; user assumes full liabilities; not liable for damages due to use or misuse; an equal opportunity employer; no shoes, no shirt, no service; quantities are limited while supplies last; if defects are discovered, do not attempt to fix them yourself, but return to an authorized service center; caveat emptor; read at your own risk; text may contain material some readers may find objectionable, parental guidance is advised; keep away from sunlight, pets, and small children; limit one-per-family please; no money down; no purchase necessary; you need not be present to win; some assembly required; batteries are not included; action figures sold separately; read and follow all label directions; no preservatives added; safety goggles may be required during use; sealed for your protection, do not use if the safety seal is broken; call before you dig; for external use only; if a rash, redness, irritation, or swelling develops, discontinue use; use only with proper ventilation; avoid extreme temperatures and store in a cool dry place; keep away from open flames and avoid inhaling fumes; do not puncture, incinerate, or store above 120 degrees Fahrenheit; do not place near flammable or magnetic source; smoking may be hazardous to your health; made from 100% recycled electrons and magnetic particles; no animals were used during testing; no salt, MSG, artificial color or flavor added; if ingested, do not induce vomiting, if symptoms persist, consult a specialist; slippery when wet; must be 18 years or older to enter; possible penalties for early withdrawal; offer valid only at participating dealers; slightly higher west of the Rockies; allow four to six six to eight weeks for delivery; disclaimer does not cover hurricane, lightning, tornado, tsunami, volcanic eruption, earthquake, flood, and other Acts of God, misuse, neglect, unauthorized repair, damage from improper installation, broken antenna or marred cabinet, incorrect line voltage, missing or altered serial numbers, sonic boom vibrations, electromagnetic radiation from nuclear blasts, customer adjustments, and incidents owing to airplane crash, ship sinking, motor vehicle accidents, leaky roof, broken glass, falling rocks, mud slides, forest fire, flying projectiles, or dropping the item; other restrictions may apply; only at participating stores; get one today; warning: pregnant women, the elderly, and children under 10 should avoid prolonged exposure; discontinue use if any of the following occurs: Itching, Vertigo, Dizziness, Tingling in extremities, Loss of balance or coordination, Slurred speech, Temporary blindness, Profuse sweating, or Heart palpitations; failure to do so relieves the makers of any and all liability; company officials were unable to be reached for comment due to the fact that no one actually tried; photos are representational only, and are not the real thing; no penalty for early reply; transportation not included; in case of a tie, the wearer may be asked to remove it; maximum achievable level of fun is unknown and may vary from group to group; not valid in the state of confusion; not responsible for errors in judgement; your rights may vary from state to state; no gifts, please.

share|improve this answer
    
doesn't this one search for a word-boundary followed by a non-word-boundary? –  grexter89 Jan 14 at 14:16
1  
@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. –  The Guy with The Hat Jan 14 at 14:17
2  
I like this one. Good catch. –  primo Jan 14 at 14:33
1  
your little characters are fun. –  xem Jan 14 at 17:05
8  
I believe you may not make a profit from it or include this in commercial publications without written permission from the President is incompatible with Stack Exchanges licenses. Your lawyer will soon be contacted. –  gerrit Jan 15 at 9:56

7 chars

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

share|improve this answer
    
You don't need the +. –  Peter Taylor Jan 13 at 17:37
10  
/[^\S\s]/ = 9 chars –  xem Jan 13 at 17:38

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.

share|improve this answer
    
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.) –  nl-x Jan 14 at 11:46
    
@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. –  Martin Büttner Jan 14 at 16:12
    
Fails in Ruby 2.0 –  Nakilon Jan 14 at 19:01
    
@Nakilon of course it does. Ruby doesn't implement the ECMAScript flavour. –  Martin Büttner Jan 14 at 19:45

6 chars

/b++b/

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

share|improve this answer
    
Huh... I just learned a new feature. Apparently, my regex skills are badly out of date. Thanks, and +1. –  Ilmari Karonen Feb 2 at 12:45

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.

share|improve this answer
    
.NET's regex engine seems to accept it. –  Bob Jan 14 at 1:45
    
And it always matches (an empty string) no matter what input on JS –  Bob Jan 14 at 1:54
    
Thanks for the testing, @Bob. –  Josh Caswell Jan 14 at 1:55

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.

share|improve this answer
    
+1 Good!! Unfortunatelly, sole 0 doesn't work in PERL. "0"=~0 is true... –  Tomas Feb 2 at 14:27
    
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. –  mirabilos Feb 3 at 13:16

5 chars

/^.^/

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

share|improve this answer
6  
Also matches the string ".^" –  boothby Jan 14 at 4:57
    
@boothby: in which language does matches? in Python doesn't. re.findall(r'^.^', '.^', re.DEBUG) –  P̲̳x͓L̳ Jan 14 at 8:39
7  
+1 for using the manga operator (see stackoverflow.com/questions/3618340/…) –  user645715 Jan 14 at 19:11
    
@boothby ^ and . are metacharacters not literal, that need to be escaped –  P̲̳x͓L̳ Jan 14 at 19:11
1  
It's broken in Perl. This question really should have set some ground rules about language. –  boothby Jan 14 at 19:28

4 char:

/.^/

Works with GNU grep 2.5.1 and egrep.

share|improve this answer
    
/.^/ = 4 chars. –  Alexey Popkov Jan 14 at 19:41
    
Why do you need the //? those are not required everywhere ;-) –  RSFalcon7 Jan 14 at 19:44
    
The wrapping slashes / count, see the original question ("including slashes and flags") and the OP's entry. –  Alexey Popkov Jan 14 at 19:48
    
right! I miss read :( –  RSFalcon7 Jan 14 at 19:49

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.

share|improve this answer

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.

share|improve this answer
1  
How does this work? –  boothby Jan 14 at 5:49
    
@boothby (*FAIL) is a verb that always fails. –  primo Jan 14 at 6:05
    
@primo you might just use /(*F)/ :) –  HamZa Jan 14 at 19:01

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
share|improve this answer
    
thanks for your answer and sorry again for the slash-counting. I thought it would be easier to include them if people used flags. –  xem Jan 15 at 7:18

4 chars

/$./

Needs any character after the string ends

share|improve this answer

6 chars

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

/{,0}/
share|improve this answer
    
Fails in Ruby 2.0 –  Nakilon Jan 14 at 19:02
    
In which regex implementations does this not give an error? –  Peter Taylor Jan 15 at 9:43
    
I only tested it using PHP's preg_match. –  Tercy Jan 15 at 13:12

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}"

share|improve this answer
    
Note that this only works in the ECMAScript flavour. In most (all?) others it is not a valid expression. –  Martin Büttner Jan 14 at 16:14
    
Isn't it invalid? –  Wasi Jan 14 at 16:14
    
@Wasi not in ECMAScript-conforming flavours –  Martin Büttner Jan 14 at 16:17
/$^/

A thing that ends before it has begun...

share|improve this answer
6  
Matches the empty string (in some RE implementations, anyways). –  Josh Caswell Jan 13 at 22:37
1  
Your implementation is broken :) –  simon Jan 13 at 22:39
2  
Better let Guido know. –  Josh Caswell Jan 13 at 22:45
6  
More importantly, as Ben Jackson pointed out, in Perl, where it doesn't match "", it does match a string containing those two literal characters: "$^". –  Josh Caswell Jan 14 at 1:44
    
+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. –  Tomas Feb 2 at 14:14

5 characters

Hope this doesnt sound stupid: /[]+/

share|improve this answer
    
Nope. Not a valid regex. –  The Guy with The Hat Jan 14 at 13:59
    
@RyanCarlson It is valid and legal... At least in Ecmascript. –  nl-x Jan 15 at 6:49

0 Chars

What about no chars or bytes, that doesn't match anything and you can't get shorter.

share|improve this answer
2  
You could argue that this isn't technically a regex. For instance, this won't compile in Python as you need a pattern. –  Ben Jan 14 at 13:25
    
@Ben you could argue that it is, perhaps with some esoteric reference to set theory. Although I grant its not in the spirit of the competition. –  Jodrell Jan 14 at 13:34
2  
Typically (ed, grep, POSIX, etc.), a 0 char regex matches the empty string anywhere it occurs. However, the fact that the OP is counting the slashes makes this dicier. –  laindir Jan 14 at 16:14
6  
That doesn't work, it matches everywhere. –  heinrich5991 Jan 15 at 9:11
1  
Also, the regex has to include two slashes. –  The Guy with The Hat Jul 22 at 16:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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