Path: csiph.com!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Les Cargill Newsgroups: comp.arch.embedded Subject: Re: Do you use FSMs or HSMs? Date: Fri, 10 Feb 2017 17:41:32 -0600 Organization: A noiseless patient Spider Lines: 61 Message-ID: References: <589902df$0$17334$c3e8da3$dd9697d2@news.astraweb.com> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Injection-Date: Fri, 10 Feb 2017 23:36:58 -0000 (UTC) Injection-Info: mx02.eternal-september.org; posting-host="e79b52b41dbd1a3991d777e86379a934"; logging-data="24929"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18BOhI/PwbwKsjGhUUWw2iQ+hx80zb5fCg=" User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:49.0) Gecko/20100101 Firefox/49.0 SeaMonkey/2.46 In-Reply-To: Cancel-Lock: sha1:rMx66hGuOTq4jMC5m3nBzYyXCnQ= Xref: csiph.com comp.arch.embedded:25819 George Neuner wrote: > On Mon, 6 Feb 2017 23:36:01 -0600, Les Cargill > wrote: > >> Clifford Heath wrote: >> >>> Lex is a language for describing a regular expression, >>> which it implements by turning it *into* an FSA. >>> >>> You don't need yacc to parse FP numbers. Such parsers >>> are for handling languages that require unbounded state, >>> not finite state. >> >> Just to be pedantic :), it's deterministic vs. non deterministic FA. >> Deterministic FA are equivalent to regular expressions. NFA >> are not, and very often, NFA are what we use for program control flow. > > Every NFA is equivalent to some DFA, and either can be mechanically > translated into the other. However the DFA version, in general, will > have many more states: in the (theoretical) worst case, equal to the > size of the power set of states in the NFA. > I've had perfectly good NFA deployed that I would hate to have to translate into a regexp :) As a practical matter ( and as you note ) , there is a very significant tactical difference. > But such explosive growth is very rare. In practice, the majority of > elements in the power set of NFA states will represent either unwanted > or redundant operations. > > >>> I'm also enthusiastic in using FSAs where appropriate, >>> but a lot of problems I face require unbounded state. >> >> This is where NFA shine - they're less formal than DFA. > > Not "less formal" per se if you are concerned about correctness. > However, in general, NFA are easier to specify and to understand. > That's the key. As you say - there may be a (small) price in the ability to demonstrate correctness. The principal advantage is the ability to generate nearly exhaustive test suites for them. It at least becomes a matter of exploiting combinators. > Any particular state of the equivalent DFA may be simultaneously > representing multiple states of the NFA. Consequently, the > transition/acceptance rules in the DFA may be extremely complex - > perhaps even incomprehensible to mere mortals. > > > George > -- Les Cargill