Editing Finite-state machine (section)

== Implementation ==

=== Hardware applications ===
[[File:4 bit counter.svg|thumb|Fig. 9 The [[circuit diagram]] for a 4-bit [[Transistor-transistor logic|TTL]] counter, a type of state machine]]
In a [[digital circuit]], an FSM may be built using a [[programmable logic device]], a [[programmable logic controller]], [[logic gate]]s and [[Flip-flop (electronics)|flip flops]] or [[relay]]s. More specifically, a hardware implementation requires a [[processor register|register]] to store state variables, a block of [[combinational logic]] that determines the state transition, and a second block of combinational logic that determines the output of an FSM. One of the classic hardware implementations is the [[Richards controller]].

In a ''Medvedev machine'', the output is directly connected to the state flip-flops minimizing the time delay between flip-flops and output.<ref>{{cite book |last= Kaeslin|first= Hubert |title=Digital Integrated Circuit Design: From VLSI Architectures to CMOS Fabrication |chapter-url=https://books.google.com/books?id=gdRStcYgf2oC&q=medvedev+fsm&pg=PA787 |year=2008 |publisher=Cambridge University Press |page=787 | chapter=Mealy, Moore, Medvedev-type and combinatorial output bits |isbn= 978-0-521-88267-5}}</ref><ref>[http://users.etech.haw-hamburg.de/users/Schwarz/En/Lecture/Ds/Notes/DigSys1.pdf Slides] {{Webarchive|url=https://web.archive.org/web/20170118123034/http://users.etech.haw-hamburg.de/users/Schwarz/En/Lecture/Ds/Notes/DigSys1.pdf |date=18 January 2017 }}, ''Synchronous Finite State Machines; Design and Behaviour'', [[University of Applied Sciences Hamburg]], p.18</ref>

Through [[state encoding for low power]] state machines may be optimized to minimize power consumption.

=== Software applications ===
The following concepts are commonly used to build software applications with finite-state machines:
* [[Automata-based programming]]
* [[Event-driven finite-state machine]]
* [[Virtual finite-state machine]]
* [[State pattern|State design pattern]]

=== Finite-state machines and compilers ===
Finite automata are often used in the [[Compilers#Front end|frontend]] of programming language compilers. Such a frontend may comprise several finite-state machines that implement a [[lexical analysis|lexical analyzer]] and a parser.
Starting from a sequence of characters, the lexical analyzer builds a sequence of language tokens (such as reserved words, literals, and identifiers) from which the parser builds a syntax tree. The lexical analyzer and the parser handle the regular and [[context-free grammar|context-free]] parts of the programming language's grammar.<ref>{{cite book |author-link1=Alfred V. Aho |last1=Aho |first1=Alfred V. |author-link2 = Ravi Sethi |last2=Sethi |first2=Ravi |author-link3=Jeffrey D. Ullman |last3=Ullman |first3=Jeffrey D. |title=Compilers: Principles, Techniques, and Tools |isbn=978-0-201-10088-4 |publisher=[[Addison-Wesley]] |year=1986 |edition=1st|title-link=Compilers: Principles, Techniques, and Tools }}</ref>