DFA illustration

What is DFA?

snipped-for-privacy@highlandsniptechnology.com Wrote in message:r

I'll vote for "Death From Above"

Cheers

Deterministic Finite Automaton. A state machine, in our lingo. I think Don is off again on one of his overly detailed things.

Jeroen Belleman

Does that mean a block of procedural code that is structured as a state macnine? That's different from the hard-clocked logic type of state machine that we do in an FPGA.

I explained the software state machine to a young engineer last month. He has an ee+ce degree and never heard of it before.

Most "hardware types" have never been exposed to automata theory. Say "State Machine" (or FINITE State Machine, to be precise) and they think "Mealy/Moore". And, how many (the minimum number of) FFs will be needed to represent the current state. And, how to minimize with implication tables. It's barely an "abstract" notion!

DFA need not have *any* "outputs" -- whereas the whole point of Mealy and Moore machines is *how* the outputs are derived from (state,inputs).

A DFA describes an *abstract machine*; a protocol can be represented in a DFA; a language/grammar can be represented in a DFA; etc. It's a conceptual model much like Petri Nets (yet another thing "hardware types" are rarely exposed to).

To answer my own question, I've two suggestions from colleagues that I'll explore, to see their practical consequences. As I said, DFA illustrations quickly get cluttered; adding MORE content increases that clutter (and *trivial* machines are hardly worth the effort to illustrate)

That's pretty much BS. I think you mean the states can be the only output. If the DFA has no outputs, it is what they term degenerate, I believe. Every machine with no outputs is equivalent as there is no way to tell them apart.

I recall using something like that in programming the EMSP, a military signal processor.

I wonder what he is doing that he needs DFA rather than FSM? I expect we will never know.

The comments about a power_off state sound a lot like a FSM.

Often there are two types of documentation for a complex FSM. One is to define what the intended functionality is (using any shortcut notation that is useful). The other is a formal FSM description using a directed graph with appropriate labels for the type of FSM, (Mealy vs. Moore or a hybrid).

The only problem with the lamentable lack of abstraction is that such state machines most always work, usually first try. There are reasons why.

That's one way to write bug-free code, have no outputs. But it could still crash.

True. We are too busy building useful things that work and sell.

Well, yes, the concept is the same, the implementation is different. I've met "software types" who were never exposed to the concept. Scandalous, if you want my opinion.

Jeroen Belleman

Likely "programmers". A good software engineering curriculum covers all of these issues as it is the basis for language design (which drives compiler design), algorithm abstractions, etc.

A hardware engineer likely never *formally* thinks of concurrency and, thus, never thinks of *modeling* it (via a Petri Net) -- design a processor and suddenly knowing what you can and can't do concurrently is of SUPREME importance! (how do you formalize what can/can't happen concurrently in your typical HARDWARE design? Just hope it's "obvious"?)

How would you design circuits without *schematics*? Those little squiggles on that sheet of paper don't *do* anything, don't consume or create energy, don't "do work", etc. They are pure abstractions. One need NEVER reify a design and yet the schematic still exists -- even if the "devices" on the schematic are purely hypothetical in nature (a diode with a 45 million PRV capable of handling 3gigaamps can still be inserted into a schematic and the resulting circuit debated -- despite it never being realizable!)

There is a subtle difference between Mealy/Moore "FSMs" (technically,

A DFA consists of a *finite* set of states a finite set of input symbols (the "alphabet") a transition function mapping (state,input) to next_state a start state a set of accept states ("destinations")

A Moore machine consistings of a finite set of states a finite set of input symbols (the "alphabet") a transition function mapping (state,input) to next_state a start state

• a finite set of outputs (the "output alphabet")
• an output function mapping each state to the output alphabet

A Mealy machine replaces the last item with

• an output function mapping each (state,inputs) to the output alphabet

A DFA is a purely abstract machine. It's a pure mathematical concept; not reified in any way. Just like a schematic is nothing more than an abstract expression of a circuit.

Note the "output tape" (in contrast to the "input tape" that contains the sequence of input symbols)

A DFA only produces a "go/no-go" result -- the machine "ran to completion" (which means attained any one of its terminal states) or not.

Every part on a schematic has a part number and a data sheet, has pins and a package, gets purchased, gets soldered to a PCB, works. Every squiggle becomes a trace or a plane on an etched PC board. None of that is abstract.

We call out real parts on schematics. We have no 45 million volt diodes in our library.

What's the difference between *finite* and finite?

Why code a DFA if it has no output and no function?

Electronic design is based on physics and predictable absolutes.

What ever happened to fuzzy logic? That was a hoot.

On 2022-09-09 22:36, John Larkin wrote: [...]

The same that happened to signature analysis. Remember that one?

Jeroen Belleman

Yes, pseudorandom logic signals and probes to see if the waveform was as expected. HP I think. Silly idea.

There have been a zillion computer language fads too. PL1, Pascal, APL, Forth, C#, C++, Python.

Don,

It is a library that takes various descriptions of state machines (regular expressions, etc) and manipulates them in various ways, including constructing DFAs.

It also emits Graphvis "dot" files that support visualisation. You would just need to augment the output with your annotations to get them on your vis.

JL: These automata are one of the most studied and most interesting things in foundational computer science. Rather than calling the whole field into question, you should try to educate yourself.

Clifford Heath

Does it generate code?

Seems awfully academic.

We had the dean of the CS dept of a big university as a house guest. I made the mistake of asking her what sort of programming they taught these days. "We don't teach programming!" Boom. Faux pas big time.

CS seems to have nothing to do with programming, maybe nothing to do with computers.

I read a popular sociology textbook just for fun, and it was. Maybe I should get a used CS text next.

I have met a lot of ce interns and grads who don't know about software state machines. Seems to me a fundamental way to code realtime, bug-free stuff... usually better than using the resources of an RTOS.

Dijkstra said that he "had no regular access to a computer."

Computer science is no more about computers than astronomy is about telescopes.

—Edsger Dijkstra

A cursory glance suggests not -- but, I will take a more detailed look. Thanks.

I have my own "home-brewed" compiler for an ASL that I created back in the early 80's for such uses. The back-end is highly configurable so I can adapt the code to a particular run-time implementation (favor time or space, etc.)

I'm not hopeful that any algorithm could avoid making a mess out of anything but trivial (or highly regular) automata. I groan each time I look at a machine-generated ERD! <frown>

And those are pretty trivial, in most cases!

I don't mind the manual effort of drawing the diagrams as I can add value by chosing judicious placement of various states.

Draw a simple state diagram -- 8-10 states. Add transitions to show a high degree of interconnectedness. Annotate each transition with some notion of the associated inputs. And, add an *action* to each. E.g., diagram a simple grammar (desk calculator?)

A *simple* diagram quickly gets cluttered!

Now, for each state, examine all of the transitions that terminate at that state. Enumerate the set of actions defined by them (presumably, they aren't all the same!). Assume I want to do something in ALL of these actions to ensure the targeted state is "set up" properly (e.g., "clear accumulator").

There is no easy way of doing this AND making it obvious to a person examining the state diagram that this "necessary condition" is in place AS that state is entered. Regardless of HOW it is entered!

If, instead, you could factor those common actions out of the individual transition actions and lump them into an OnEntry() action that you declare for that (each) state, then this ensures you don't forget to add those actions to "transition X from state Y". And, draws attention to them as a preset for state Z.

Ditto for every transition exiting that state -- so you don't have to remember to include them in every action associated with those transitions (and also highlighting those activities to the reader)

Where do you put those declarations (in the *diagram*) and what form should they take to make them obvious to the reader -- without eating up lots of space (which limits the complexity/size of the automaton that you can illustrate!)

One way to handle the OnEntry mechanism is to add a "preset" state upstream of each destination state. All transitions intended for STATE are, instead, routed to this PRESTATE. (you must exercise discipline or force compiler to impose it) PRESTATE then has a single "always" transition that connects it to STATE and invokes the OnEntry actions required on that transition.

But, now you've double the number of states to illustrate.

And, how do you address the OnExit issue? (use a PDA?)

You can put the action (function) *in* the state circle with some sort of identification ("In/Entry", "Out/Exit") -- but that means the state circles get larger to accommodate. (Hint: there's more space OUTSIDE than IN! But, the "outside" is cluttered with transition vectors!)

Consider that most automata aren't the trivial sorts of examples you see in the literature and its easy to see how a diagram can quickly become unmanageable.

Returning to your suggestion (libfsm), I didn't see anything that indicated support for this sort of "annotation". Or, even suggestions of where it *might* put it. But, I'll have a look at it, tonight.

Dunning-Kruger

Jeez Don, if you want to know how to use Graphvis, you should just read the flaming documentation, not write an epistle here. It's not perfect, but it's worth at least looking at before you start complaining about it.