help-gnu-emacs
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: How are regexen implemented in Emacs?


From: Emanuel Berg
Subject: Re: How are regexen implemented in Emacs?
Date: Thu, 15 Dec 2022 06:18:36 +0100
User-agent: Gnus/5.13 (Gnus v5.13)

tomas wrote:

> Nitpick: The Emacs regexp engine is a FA based one, but
> a DFA, not a NFA (the famous Thompson NFA).

DFA = Deterministic finite automaton
NFA = Nondeterministic finite automaton

Finite - it's a state machine, finite means the number of
states are not infinite.

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?

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?

-- 
underground experts united
https://dataswamp.org/~incal




reply via email to

[Prev in Thread] Current Thread [Next in Thread]