{"id":36,"date":"2012-04-02T10:47:04","date_gmt":"2012-04-02T10:47:04","guid":{"rendered":"http:\/\/www.vidarholen.net\/contents\/blog\/?p=36"},"modified":"2012-04-02T10:58:14","modified_gmt":"2012-04-02T10:58:14","slug":"technically-correct-inversed-regex","status":"publish","type":"post","link":"https:\/\/www.vidarholen.net\/contents\/blog\/?p=36","title":{"rendered":"Technically correct: Inversed regex"},"content":{"rendered":"

How do I write a regex that matches lines that do not<\/strong> contain hi<\/code>?<\/p><\/blockquote>\n

That’s a frequently asked question if I ever saw one.<\/p>\n

Of course, the proper answer is: you don’t. You write a regex that does<\/strong> match hi<\/code> and then invert the matching logic, ostensibly with grep -v<\/code>. But where’s the fun in that?<\/p>\n

One interesting theorem that pops up in any book or class on formal grammars is that regular languages are closed under complement: the inverse of a regular expression is also a regular expression. This means that writing inverted regular expressions is theoretically possible, though it turns out to be quite tricky <\/p>\n

Just try writing a regex that matches strings that does not contain “hi”, and test it against “hi”, “hhi” and “ih”, “iih” and such variations. Some solutions are coming up. <\/p>\n

A way to cheat is using PCRE negative lookahead: ^(?!.*foo)<\/code> matches all strings not containing the substring “foo”. However, lookahead assertions require a stack, and thus can’t be modelled as a finite state machine. In other words, they don’t fit the mathematical definition of a regular expression, and therefore disqualify.<\/p>\n

There are simple, well-known algorithms for turning regular expressions into non-deterministic finite automata, and from there to deterministic FA. Less commonly used and known are algorithms for inverting a DFA and for generating familiar textual regex from it. <\/p>\n

You can find these described in various<\/a> lecture notes and slides<\/a>, so I won’t recite them. <\/p>\n

What I had a harder time finding was software that actually did this. So here<\/a> is a Haskell program. It’s highly suboptimal but it does the job. When executed, it will ask for a regex and will then output a grep command that matches everything the regex does not (without -v<\/code>, obviously). <\/p>\n

The expressions it produces are quite horrific; it’s computer generated code, after all. <\/p>\n

A regular expression for matching strings that do not match .*hi.*<\/code> could be grep -E '^([^h]|h+$|h+[^hi])*$'<\/code>.<\/p>\n

This app, however, suggests grep -E '^([^h]([^h]|)*||([^h][^h]*h|h)|([^h][^h]*(h(hh*[^hi]|[^hi]))|(h(hh*[^hi]|[^hi])))((hh*[^hi]|[^h])|)*|([^h][^h]*(h([^hi][^h]*h|h))|(h([^hi][^h]*h|h)))(([^hi][^h]*h|h)|)*)$'<\/code><\/p>\n

It still works exactly as stated though!<\/p>\n

The app just supports a small subset of regex, just enough to convince someone that it works, and as a party trick lets you answer the original question exactly as stated. <\/p>\n

Technically correct is the best kind of correct. <\/p>\n","protected":false},"excerpt":{"rendered":"

How do I write a regex that matches lines that do not contain hi? That’s a frequently asked question if I ever saw one. Of course, the proper answer is: you don’t. You write a regex that does match hi and then invert the matching logic, ostensibly with grep -v. But where’s the fun in … Continue reading “Technically correct: Inversed regex”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":"","jetpack_publicize_message":"","jetpack_is_tweetstorm":false,"jetpack_publicize_feature_enabled":true},"categories":[5,4,23],"tags":[42,41,40],"class_list":["post-36","post","type-post","status-publish","format-standard","hentry","category-advanced-linux","category-linux","category-programming","tag-compsci","tag-regex","tag-technically-correct"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=\/wp\/v2\/posts\/36","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=36"}],"version-history":[{"count":0,"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=\/wp\/v2\/posts\/36\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=36"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=36"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.vidarholen.net\/contents\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=36"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}