# Regular Expression question

Notepad++ has a "regular expression" search but it does not implement the pipe OR | operator, which allows you to take two regular expressions and union them into another regular expression. As we know, regexes are closed under three operations, union, concatenation, and Kleene star, implemented by |, implicitly, and by * respectively (or their respective backslash-escaped counterparts, depending on host language).

Does this mean that Notepad++'s implementation is incomplete (i.e. it does not allow searching regular expressions so therefore this is false advertisement of features)? Or am I missing something by jumping to that conclusion? After all, only the most straightforward way of constructing a unioned language is unavailable to me, I need to prove that I cannot construct the language using any combination of remaining operators available in order to have an actual counter-example.

But it stands to reason that without my pipe I see no way of simply specifying a match for ab|ba using any other combination and yet this is clearly a regular expression. Is that counterexample enough? (thanks for corrections for this counterexample folks)

http://scintilla.org/SciTERegEx.html outlines the available operators.

-
Can you give a full list of operators that are available? – Raphael Sep 8 '11 at 8:01
@Raphael, It uses scintilla, and this appears to be a list of operators available with it: scintilla.org/SciTERegEx.html – Steven Lu Sep 8 '11 at 8:16
The description: "a composite regular expression xy ... matches the longest match of x followed by a match for y" (emphasis added) strongly suggests to me that the author of the library knew no regular language theory and just uses ad-hoc matching methods such as backtracking. On that background it is not surprising if the library fails to express all regular languages. – Henning Makholm Sep 8 '11 at 12:13
@Henning, what it means is that it defaults to greedy matching. There is a lazy quantifier. It's POSIX regex with some custom extensions. – Peter Taylor Sep 8 '11 at 13:05
Can you include the link in your comment in the question so that people can understand the precise question without reading comments? – Tsuyoshi Ito Sep 8 '11 at 16:37

It's a complete - in fact, more than complete, because it adds some features - implementation of POSIX Basic Regular Expressions. However, POSIX BREs are not regular expressions in the Chomsky-hierarchy sense.

The problem is that "regular expression" has to be decoded by context. Many regex engines nowadays handle far more powerful tools than are available in regular expressions. People who've studied the Chomsky hierarchy may use "regular expression" as a technical term with the meaning you understand (a pattern mechanism for matching regular languages) and "regex" as a technical term which covers a variety of similar pattern matching mechanisms which may be more powerful, less powerful, or (as in this case) incomparable. But people who haven't studied the Chomsky hierarchy often don't realise that there's a distinction.

-
Are you sure that POSIX BRE is at least as powerful as regular expressions in formal language theory? I fail to see how to write a POSIX BRE for the regular expression ab|ba. – Tsuyoshi Ito Sep 8 '11 at 16:32
@Tsuyoshi, if it's possible to interpret what I've written as saying that BRE is as powerful as Chomsky-hierarchy regular expressions then I need to rewrite. The point I'm trying to make is that they aren't. – Peter Taylor Sep 8 '11 at 17:31
I thought that “complete” in the question (hence also in your answer) means that BRE is as powerful as regular expressions. If not, I do not know what it is supposed to mean. – Tsuyoshi Ito Sep 8 '11 at 18:01
@Tsuyoshi, given that I only use the word "complete" as part of the noun phrase "complete implementation of POSIX Basic Regular Expressions" I still don't see how it can be interpreted as implying anything about the power of BREs. – Peter Taylor Sep 12 '11 at 12:16
I see. I did not read the answer carefully. Sorry for that. Still, I think that it is easy to see why I misinterpreted your answer, given that (as I explained in my previous comment) I consider that the word “complete” in the question means that it is as powerful as regular expressions in formal language theory. – Tsuyoshi Ito Sep 12 '11 at 12:47

Regular expressions without | describe union-free regular languages. I'm making this CW; the credit goes to Hermann Gruber at cst.se who answered my slightly broader question there, which see.

-
Note that the POSIX BREs discussed here aren't regular, because they have back-references. – Peter Taylor Sep 10 '11 at 6:21