regex - Regular expression to match a line that doesn't contain a word

Since no one else has given a direct answer to the question that was asked, I'll do it.

The answer is that with POSIX grep, it's impossible to literally satisfy this request:

grep "" input

The reason is that POSIX grep is only required to work with Basic Regular Expressions, which are simply not powerful enough for accomplishing that task (they are not capable of parsing regular languages, because of lack of alternation and parentheses).

However, GNU grep implements extensions that allow it. In particular, \| is the alternation operator in GNU's implementation of BREs, and \( and \) are the parentheses. If your regular expression engine supports alternation, negative bracket expressions, parentheses and the Kleene star, and is able to anchor to the beginning and end of the string, that's all you need for this approach. Note however that negative sets [^ ... ] are very convenient in addition to those, because otherwise, you need to replace them with an expression of the form (a|b|c| ... ) that lists every character that is not in the set, which is extremely tedious and overly long, even more so if the whole character set is Unicode.

With GNU grep, the answer would be something like:

grep "^\([^h]\|h\(h\|eh\|edh\)*\([^eh]\|e[^dh]\|ed[^eh]\)\)*\(\|h\(h\|eh\|edh\)*\(\|e\|ed\)\)$" input

(found with Grail and some further optimizations made by hand).

You can also use a tool that implements Extended Regular Expressions, like egrep, to get rid of the backslashes:

egrep "^([^h]|h(h|eh|edh)*([^eh]|e[^dh]|ed[^eh]))*(|h(h|eh|edh)*(|e|ed))$" input

Here's a script to test it (note it generates a file testinput.txt in the current directory):

#!/bin/bash
REGEX="^\([^h]\|h\(h\|eh\|edh\)*\([^eh]\|e[^dh]\|ed[^eh]\)\)*\(\|h\(h\|eh\|edh\)*\(\|e\|ed\)\)$"
# First four lines as in OP's testcase.
cat > testinput.txt <hoho
hihi
haha
hede
h
he
ah
head
ahead
ahed
aheda
ahede
hhede
hehede
hedhede
hehehehehehedehehe
hedecidedthat
EOF
diff -s -u <(grep -v hede testinput.txt) <(grep "$REGEX" testinput.txt)

In my system it prints:

Files /dev/fd/63 and /dev/fd/62 are identical

as expected.

For those interested in the details, the technique employed is to convert the regular expression that matches the word into a finite automaton, then invert the automaton by changing every acceptance state to non-acceptance and vice versa, and then converting the resulting FA back to a regular expression.

Finally, as everyone has noted, if your regular expression engine supports negative lookahead, that simplifies the task a lot. For example, with GNU grep:

grep -P '^((?!hede).)*$' input

Update: I have recently found Kendall Hopkins' excellent FormalTheory library, written in PHP, which provides a functionality similar to Grail. Using it, and a simplifier written by myself, I've been able to write an online generator of negative regular expressions given an input phrase (only alphanumeric and space characters currently supported): http://www.formauri.es/personal/pgimeno/misc/non-match-regex/

For hede it outputs:

^([^h]|h(h|e(h|dh))*([^eh]|e([^dh]|d[^eh])))*(h(h|e(h|dh))*(ed?)?)?$

which is equivalent to the above.