From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Newsgroups: gmane.emacs.help Subject: Re: How are regexen implemented in Emacs? Date: Thu, 15 Dec 2022 14:38:45 +0100 Message-ID: References: <87a63see6m.fsf@mbork.pl> <877cywe8w9.fsf@mbork.pl> <87r0x1utw3.fsf@dataswamp.org> Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="KpcdWKCFGSoD9ZEB" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="35281"; mail-complaints-to="usenet@ciao.gmane.io" To: help-gnu-emacs@gnu.org Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane-mx.org@gnu.org Thu Dec 15 14:39:19 2022 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1p5oSF-00090L-48 for geh-help-gnu-emacs@m.gmane-mx.org; Thu, 15 Dec 2022 14:39:19 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1p5oRn-00029b-7s; Thu, 15 Dec 2022 08:38:51 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1p5oRl-000262-Ob for help-gnu-emacs@gnu.org; Thu, 15 Dec 2022 08:38:49 -0500 Original-Received: from mail.tuxteam.de ([5.199.139.25]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1p5oRj-0006je-W2 for help-gnu-emacs@gnu.org; Thu, 15 Dec 2022 08:38:49 -0500 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=tuxteam.de; s=mail; h=From:In-Reply-To:Content-Type:MIME-Version:References:Message-ID: Subject:To:Date:Sender:Reply-To:Cc:Content-Transfer-Encoding:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=nRbvrnfWuJwuiEKWOVb5dR6s6MbREMvYXFGqnKUlIuA=; b=l96DS7ut8o21nkQmM23WCVYGxe 8OfmWJBIfmBSdX8qfppERardiKsTfHWn67bfXiF45phl/jtoMbMc+KJzv1wXD27kM7lC4JFrzR/+/ RnvSb7VHULAa9AlznHmcCyo6HwJLJjebNzkZo20XBc6JriSGy8j3Qs20ah98Hvlrw1FzIHAI0/OJf LmYByVTi1J7oJudrWJMtplaOJ+N4wcOKY/Uhz4pwe3C0oOC0dPDFPFoQwqRSu5PciogI2Nh1kaoan cqT983wApe68Jasg37GAH11Hd14JD+d/cbZcnY8NqN3oueBsUnMgzXJgmBN/RPDdK1gqvMM/lwtYV XJMriQkg==; Original-Received: from tomas by mail.tuxteam.de with local (Exim 4.94.2) (envelope-from ) id 1p5oRh-0001a8-JV for help-gnu-emacs@gnu.org; Thu, 15 Dec 2022 14:38:45 +0100 Content-Disposition: inline In-Reply-To: <87r0x1utw3.fsf@dataswamp.org> Received-SPF: pass client-ip=5.199.139.25; envelope-from=tomas@tuxteam.de; helo=mail.tuxteam.de X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.help:141766 Archived-At: --KpcdWKCFGSoD9ZEB Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Thu, Dec 15, 2022 at 06:18:36AM +0100, Emanuel Berg wrote: [...] > A set of rules crunches the input and determines transitions > from one state to another, I can imagine deterministic such > rules - but nondeterministic, what does that mean? >=20 > Maybe that from one state S and input I there are not one but > several ways to go, one can go to S' but also S'' and both > "moves" are legal? Exactly. The naive implementation of which involves keeping a queue of possible states (breadth-first search). Thompson's trick is converting the NFA into a DFA by considering "sets of (possible) states" as your new states. But now you've got 2^n states; the clever part is how to reduce that to some manageable state space. I think the Wikipedia has good articles on that. Cheers --=20 t --KpcdWKCFGSoD9ZEB Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iF0EABECAB0WIQRp53liolZD6iXhAoIFyCz1etHaRgUCY5sjXwAKCRAFyCz1etHa RoclAJ9gPWhYoh/D3FXVhmLU6jUYagyNiwCfcBvLXAIBzTJQFrANx+5BXnlKoro= =GbzF -----END PGP SIGNATURE----- --KpcdWKCFGSoD9ZEB--