unofficial mirror of help-gnu-emacs@gnu.org
 help / color / mirror / Atom feed
From: Anders Munch <ajm@flonidan.dk>
To: help-gnu-emacs <help-gnu-emacs@gnu.org>
Subject: RE: How to get a concatenation of the negations with rx (ex: [^a][^b])?
Date: Mon, 13 Nov 2023 08:46:15 +0000	[thread overview]
Message-ID: <VI1PR05MB106809A8B9B549FA23CDA3BF5B4B3A@VI1PR05MB10680.eurprd05.prod.outlook.com> (raw)
In-Reply-To: <ZVCrJbkdmP6oJ8dX@tuxteam.de>

tomas@tuxteam.de wrote:
> OK -- this was roughly my train of thought: build the NFA, then invert that... OMG. Then I decided this is better left as an exercise to the reader.

At the DFA level it's easy.  So you can just convert the NFA to a DFA and work from there.  I did that exercise once upon a time, let me see if I can remember it.

First convert to DFA. For every node, add an outgoing edge to the acceptance state for every character that doesn't already have an outgoing node. Remove all edges to the acceptance state that were in the original DFA.

The main problem is not implementation.  It's that it's not obvious what to use them for in the variable-length searches that regexes are typically used for.  It's just confusing that the string "abz" is a match for the regular expression "not ab", and if you were looking for a two-character string that is not "ab", then a general negation operator isn't going to help you, at least not by itself.

regards,
Anders


  parent reply	other threads:[~2023-11-13  8:46 UTC|newest]

Thread overview: 11+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2023-11-11 20:17 How to get a concatenation of the negations with rx (ex: [^a][^b])? Edgar Lux
2023-11-11 21:00 ` Emanuel Berg
2023-11-13 19:26   ` tomas
2023-11-12  7:03 ` Michael Heerdegen
2023-11-12  7:26   ` tomas
2023-11-12  8:28     ` Yuri Khan
2023-11-12 10:38       ` tomas
2023-11-12 11:53         ` Michael Heerdegen
2023-11-13  8:46         ` Anders Munch [this message]
2023-11-13  9:24           ` tomas
2023-12-24 11:54             ` tomas

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: https://www.gnu.org/software/emacs/

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=VI1PR05MB106809A8B9B549FA23CDA3BF5B4B3A@VI1PR05MB10680.eurprd05.prod.outlook.com \
    --to=ajm@flonidan.dk \
    --cc=help-gnu-emacs@gnu.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body. 
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).