Just began studying automata. I've already seen several examples of the applications of finite automata: pattern matching, automatic doors, etc. And so far, I understand the logical connection between those mechanisms and state diagrams and formal definitions. But I'm curious, what thing is implementing time steps—if that's what they're called—allowing states to transition. I know a tiny bit about computer architecture so I'm thinking it's like a processor clock, you know, something just ticking on and off very rapidly. Then the automata takes input on every "tick" of said clock. But with different devices using different current types (AC/DC) how is this actually being accomplished in an arbitrary physical device?

Now that I'm writing this out, it seems clear there are multiple ways to accomplish that ticking depending on what we're talking about, but I'm just looking for the most common examples found in real-life. For example what is allowing the sequence of input signals to occur in an automatic door?


1 Answer 1


A synchronous system with a clock is not necessary. The transition between states can be triggered asynchronously by inputs to the system (e.g. someone pushes a button to operate an automatic door). The finite state machine needs to have some logic elements to "remember" of what state it is currently in, but that does not have to be anything like the addressable memory used in digital computer system. It could simply be a set of mechanical switches and electrical relays.

For example a mechanical combination lock is an example of an asynchronous finite state machine where the "memory" is just the physical positions of the different parts of the lock.

To interface the real world inputs to a synchronous control system such as a digital computer, there are two basic techniques: either the computer program regularly polls the input devices to check what state they are in, or the input devices generate interrupts which force the program to jump to a different point and continue executing from there. Textbooks on computer system design explain both methods in detail.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.