5
$\begingroup$

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.

  • 1
    Can you include the link in your comment in the question so that people can understand the precise question without reading comments?2011-09-08

2 Answers 2

3

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.

  • 0
    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.2011-09-12
1

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.

  • 1
    Note that the POSIX BREs discussed here aren't regular, because they have back-references.2011-09-10