CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Finite-state machine - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"5844479b-5d31-49ba-9108-d8062e94412d","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Finite-state_machine","wgTitle":"Finite-state machine","wgCurRevisionId":1246478939,"wgRevisionId":1246478939,"wgArticleId":10931,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["CS1: long volume value","All articles with dead external links","Articles with dead external links from October 2017","Articles with permanently dead external links","Webarchive template wayback links","Articles with short description","Short description is different from Wikidata","Use dmy dates from January 2020","Wikipedia articles needing clarification from March 2021","All articles with unsourced statements","Articles with unsourced statements from March 2021", "Articles with unsourced statements from January 2017","All articles that are too technical","Wikipedia articles that are too technical from January 2017","All articles needing expert attention","Articles needing expert attention from January 2017","Finite automata","Management cybernetics"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Finite-state_machine","wgRelevantArticleId":10931,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true}, "wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":40000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q176452","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.imagemap.styles":"ready","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready", "jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.imagemap","ext.cite.ux-enhancements","mediawiki.page.media","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.imagemap.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/a/a2/Automata_theory.svg/1200px-Automata_theory.svg.png"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="900"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/a/a2/Automata_theory.svg/800px-Automata_theory.svg.png"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="600"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/a/a2/Automata_theory.svg/640px-Automata_theory.svg.png"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="480"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Finite-state machine - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Finite-state_machine"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Finite-state_machine&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Finite-state_machine"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Finite-state_machine rootpage-Finite-state_machine skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Finite-state+machine" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Finite-state+machine" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Finite-state+machine" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Finite-state+machine" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Example:_coin-operated_turnstile" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Example:_coin-operated_turnstile"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Example: coin-operated turnstile</span> </div> </a> <ul id="toc-Example:_coin-operated_turnstile-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Concepts_and_terminology" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Concepts_and_terminology"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Concepts and terminology</span> </div> </a> <ul id="toc-Concepts_and_terminology-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Representations" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Representations"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Representations</span> </div> </a> <button aria-controls="toc-Representations-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Representations subsection</span> </button> <ul id="toc-Representations-sublist" class="vector-toc-list"> <li id="toc-State/Event_table" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#State/Event_table"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1</span> <span>State/Event table</span> </div> </a> <ul id="toc-State/Event_table-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-UML_state_machines" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#UML_state_machines"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.2</span> <span>UML state machines</span> </div> </a> <ul id="toc-UML_state_machines-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-SDL_state_machines" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#SDL_state_machines"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.3</span> <span>SDL state machines</span> </div> </a> <ul id="toc-SDL_state_machines-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Other_state_diagrams" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Other_state_diagrams"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.4</span> <span>Other state diagrams</span> </div> </a> <ul id="toc-Other_state_diagrams-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Usage" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Usage"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Usage</span> </div> </a> <ul id="toc-Usage-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Classification" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Classification"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Classification</span> </div> </a> <button aria-controls="toc-Classification-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Classification subsection</span> </button> <ul id="toc-Classification-sublist" class="vector-toc-list"> <li id="toc-Acceptors" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Acceptors"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.1</span> <span>Acceptors</span> </div> </a> <ul id="toc-Acceptors-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Classifiers" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Classifiers"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.2</span> <span>Classifiers</span> </div> </a> <ul id="toc-Classifiers-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Transducers" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Transducers"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.3</span> <span>Transducers</span> </div> </a> <ul id="toc-Transducers-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Sequencers" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Sequencers"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.4</span> <span>Sequencers</span> </div> </a> <ul id="toc-Sequencers-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Determinism" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Determinism"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.5</span> <span>Determinism</span> </div> </a> <ul id="toc-Determinism-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Alternative_semantics" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Alternative_semantics"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Alternative semantics</span> </div> </a> <ul id="toc-Alternative_semantics-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Mathematical_model" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Mathematical_model"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Mathematical model</span> </div> </a> <ul id="toc-Mathematical_model-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Optimization" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Optimization"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>Optimization</span> </div> </a> <ul id="toc-Optimization-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Implementation" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Implementation"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>Implementation</span> </div> </a> <button aria-controls="toc-Implementation-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Implementation subsection</span> </button> <ul id="toc-Implementation-sublist" class="vector-toc-list"> <li id="toc-Hardware_applications" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Hardware_applications"> <div class="vector-toc-text"> <span class="vector-toc-numb">9.1</span> <span>Hardware applications</span> </div> </a> <ul id="toc-Hardware_applications-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Software_applications" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Software_applications"> <div class="vector-toc-text"> <span class="vector-toc-numb">9.2</span> <span>Software applications</span> </div> </a> <ul id="toc-Software_applications-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Finite-state_machines_and_compilers" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Finite-state_machines_and_compilers"> <div class="vector-toc-text"> <span class="vector-toc-numb">9.3</span> <span>Finite-state machines and compilers</span> </div> </a> <ul id="toc-Finite-state_machines_and_compilers-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">10</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">11</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Further_reading" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Further_reading"> <div class="vector-toc-text"> <span class="vector-toc-numb">12</span> <span>Further reading</span> </div> </a> <button aria-controls="toc-Further_reading-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Further reading subsection</span> </button> <ul id="toc-Further_reading-sublist" class="vector-toc-list"> <li id="toc-General" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#General"> <div class="vector-toc-text"> <span class="vector-toc-numb">12.1</span> <span>General</span> </div> </a> <ul id="toc-General-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Finite-state_machines_(automata_theory)_in_theoretical_computer_science" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Finite-state_machines_(automata_theory)_in_theoretical_computer_science"> <div class="vector-toc-text"> <span class="vector-toc-numb">12.2</span> <span>Finite-state machines (automata theory) in theoretical computer science</span> </div> </a> <ul id="toc-Finite-state_machines_(automata_theory)_in_theoretical_computer_science-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Abstract_state_machines_in_theoretical_computer_science" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Abstract_state_machines_in_theoretical_computer_science"> <div class="vector-toc-text"> <span class="vector-toc-numb">12.3</span> <span>Abstract state machines in theoretical computer science</span> </div> </a> <ul id="toc-Abstract_state_machines_in_theoretical_computer_science-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Machine_learning_using_finite-state_algorithms" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Machine_learning_using_finite-state_algorithms"> <div class="vector-toc-text"> <span class="vector-toc-numb">12.4</span> <span>Machine learning using finite-state algorithms</span> </div> </a> <ul id="toc-Machine_learning_using_finite-state_algorithms-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Hardware_engineering:_state_minimization_and_synthesis_of_sequential_circuits" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Hardware_engineering:_state_minimization_and_synthesis_of_sequential_circuits"> <div class="vector-toc-text"> <span class="vector-toc-numb">12.5</span> <span>Hardware engineering: state minimization and synthesis of sequential circuits</span> </div> </a> <ul id="toc-Hardware_engineering:_state_minimization_and_synthesis_of_sequential_circuits-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Finite_Markov_chain_processes" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Finite_Markov_chain_processes"> <div class="vector-toc-text"> <span class="vector-toc-numb">12.6</span> <span>Finite Markov chain processes</span> </div> </a> <ul id="toc-Finite_Markov_chain_processes-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">13</span> <span>External links</span> </div> </a> <ul id="toc-External_links-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Finite-state machine</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 43 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-43" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">43 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D8%A2%D9%84%D8%A9_%D9%85%D8%AD%D8%AF%D9%88%D8%AF%D8%A9_%D8%A7%D9%84%D8%AD%D8%A7%D9%84%D8%A7%D8%AA" title="آلة محدودة الحالات – Arabic" lang="ar" hreflang="ar" data-title="آلة محدودة الحالات" data-language-autonym="العربية" data-language-local-name="Arabic" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-bg mw-list-item"><a href="https://bg.wikipedia.org/wiki/%D0%9A%D1%80%D0%B0%D0%B5%D0%BD_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82" title="Краен автомат – Bulgarian" lang="bg" hreflang="bg" data-title="Краен автомат" data-language-autonym="Български" data-language-local-name="Bulgarian" class="interlanguage-link-target"><span>Български</span></a></li><li class="interlanguage-link interwiki-bs mw-list-item"><a href="https://bs.wikipedia.org/wiki/Kona%C4%8Dni_automat" title="Konačni automat – Bosnian" lang="bs" hreflang="bs" data-title="Konačni automat" data-language-autonym="Bosanski" data-language-local-name="Bosnian" class="interlanguage-link-target"><span>Bosanski</span></a></li><li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Aut%C3%B2mat_finit" title="Autòmat finit – Catalan" lang="ca" hreflang="ca" data-title="Autòmat finit" data-language-autonym="Català" data-language-local-name="Catalan" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/Kone%C4%8Dn%C3%BD_automat" title="Konečný automat – Czech" lang="cs" hreflang="cs" data-title="Konečný automat" data-language-autonym="Čeština" data-language-local-name="Czech" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Endlicher_Automat" title="Endlicher Automat – German" lang="de" hreflang="de" data-title="Endlicher Automat" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-et mw-list-item"><a href="https://et.wikipedia.org/wiki/L%C3%B5plik_olekumasin" title="Lõplik olekumasin – Estonian" lang="et" hreflang="et" data-title="Lõplik olekumasin" data-language-autonym="Eesti" data-language-local-name="Estonian" class="interlanguage-link-target"><span>Eesti</span></a></li><li class="interlanguage-link interwiki-es badge-Q17437798 badge-goodarticle mw-list-item" title="good article badge"><a href="https://es.wikipedia.org/wiki/Aut%C3%B3mata_finito" title="Autómata finito – Spanish" lang="es" hreflang="es" data-title="Autómata finito" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-eo mw-list-item"><a href="https://eo.wikipedia.org/wiki/Finia_a%C5%ADtomato" title="Finia aŭtomato – Esperanto" lang="eo" hreflang="eo" data-title="Finia aŭtomato" data-language-autonym="Esperanto" data-language-local-name="Esperanto" class="interlanguage-link-target"><span>Esperanto</span></a></li><li class="interlanguage-link interwiki-eu mw-list-item"><a href="https://eu.wikipedia.org/wiki/Automata_finitu" title="Automata finitu – Basque" lang="eu" hreflang="eu" data-title="Automata finitu" data-language-autonym="Euskara" data-language-local-name="Basque" class="interlanguage-link-target"><span>Euskara</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D9%85%D8%A7%D8%B4%DB%8C%D9%86_%D8%AD%D8%A7%D9%84%D8%A7%D8%AA_%D9%85%D8%AA%D9%86%D8%A7%D9%87%DB%8C" title="ماشین حالات متناهی – Persian" lang="fa" hreflang="fa" data-title="ماشین حالات متناهی" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Automate_fini" title="Automate fini – French" lang="fr" hreflang="fr" data-title="Automate fini" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-gl mw-list-item"><a href="https://gl.wikipedia.org/wiki/Aut%C3%B3mata_finito" title="Autómata finito – Galician" lang="gl" hreflang="gl" data-title="Autómata finito" data-language-autonym="Galego" data-language-local-name="Galician" class="interlanguage-link-target"><span>Galego</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%95%9C_%EC%83%81%ED%83%9C_%EA%B8%B0%EA%B3%84" title="유한 상태 기계 – Korean" lang="ko" hreflang="ko" data-title="유한 상태 기계" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-hy mw-list-item"><a href="https://hy.wikipedia.org/wiki/%D5%8E%D5%A5%D6%80%D5%BB%D5%A1%D5%BE%D5%B8%D6%80_%D5%A1%D5%BE%D5%BF%D5%B8%D5%B4%D5%A1%D5%BF" title="Վերջավոր ավտոմատ – Armenian" lang="hy" hreflang="hy" data-title="Վերջավոր ավտոմատ" data-language-autonym="Հայերեն" data-language-local-name="Armenian" class="interlanguage-link-target"><span>Հայերեն</span></a></li><li class="interlanguage-link interwiki-hr mw-list-item"><a href="https://hr.wikipedia.org/wiki/Kona%C4%8Dni_automat" title="Konačni automat – Croatian" lang="hr" hreflang="hr" data-title="Konačni automat" data-language-autonym="Hrvatski" data-language-local-name="Croatian" class="interlanguage-link-target"><span>Hrvatski</span></a></li><li class="interlanguage-link interwiki-id mw-list-item"><a href="https://id.wikipedia.org/wiki/Mesin_finite-state" title="Mesin finite-state – Indonesian" lang="id" hreflang="id" data-title="Mesin finite-state" data-language-autonym="Bahasa Indonesia" data-language-local-name="Indonesian" class="interlanguage-link-target"><span>Bahasa Indonesia</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Automa_a_stati_finiti" title="Automa a stati finiti – Italian" lang="it" hreflang="it" data-title="Automa a stati finiti" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%90%D7%95%D7%98%D7%95%D7%9E%D7%98_%D7%A1%D7%95%D7%A4%D7%99" title="אוטומט סופי – Hebrew" lang="he" hreflang="he" data-title="אוטומט סופי" data-language-autonym="עברית" data-language-local-name="Hebrew" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-ka mw-list-item"><a href="https://ka.wikipedia.org/wiki/%E1%83%A1%E1%83%90%E1%83%A1%E1%83%A0%E1%83%A3%E1%83%9A%E1%83%98_%E1%83%9B%E1%83%90%E1%83%9C%E1%83%A5%E1%83%90%E1%83%9C%E1%83%90" title="სასრული მანქანა – Georgian" lang="ka" hreflang="ka" data-title="სასრული მანქანა" data-language-autonym="ქართული" data-language-local-name="Georgian" class="interlanguage-link-target"><span>ქართული</span></a></li><li class="interlanguage-link interwiki-lv mw-list-item"><a href="https://lv.wikipedia.org/wiki/Gal%C4%ABgs_autom%C4%81ts" title="Galīgs automāts – Latvian" lang="lv" hreflang="lv" data-title="Galīgs automāts" data-language-autonym="Latviešu" data-language-local-name="Latvian" class="interlanguage-link-target"><span>Latviešu</span></a></li><li class="interlanguage-link interwiki-lt mw-list-item"><a href="https://lt.wikipedia.org/wiki/Baigtinis_automatas" title="Baigtinis automatas – Lithuanian" lang="lt" hreflang="lt" data-title="Baigtinis automatas" data-language-autonym="Lietuvių" data-language-local-name="Lithuanian" class="interlanguage-link-target"><span>Lietuvių</span></a></li><li class="interlanguage-link interwiki-lmo mw-list-item"><a href="https://lmo.wikipedia.org/wiki/Automa_a_stat_finii" title="Automa a stat finii – Lombard" lang="lmo" hreflang="lmo" data-title="Automa a stat finii" data-language-autonym="Lombard" data-language-local-name="Lombard" class="interlanguage-link-target"><span>Lombard</span></a></li><li class="interlanguage-link interwiki-mk mw-list-item"><a href="https://mk.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%B5%D0%BD_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82" title="Конечен автомат – Macedonian" lang="mk" hreflang="mk" data-title="Конечен автомат" data-language-autonym="Македонски" data-language-local-name="Macedonian" class="interlanguage-link-target"><span>Македонски</span></a></li><li class="interlanguage-link interwiki-mwl mw-list-item"><a href="https://mwl.wikipedia.org/wiki/Out%C3%B3mato_fenito" title="Outómato fenito – Mirandese" lang="mwl" hreflang="mwl" data-title="Outómato fenito" data-language-autonym="Mirandés" data-language-local-name="Mirandese" class="interlanguage-link-target"><span>Mirandés</span></a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Eindigetoestandsautomaat" title="Eindigetoestandsautomaat – Dutch" lang="nl" hreflang="nl" data-title="Eindigetoestandsautomaat" data-language-autonym="Nederlands" data-language-local-name="Dutch" class="interlanguage-link-target"><span>Nederlands</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E6%9C%89%E9%99%90%E3%82%AA%E3%83%BC%E3%83%88%E3%83%9E%E3%83%88%E3%83%B3" title="有限オートマトン – Japanese" lang="ja" hreflang="ja" data-title="有限オートマトン" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-no mw-list-item"><a href="https://no.wikipedia.org/wiki/Endelig_tilstandsmaskin" title="Endelig tilstandsmaskin – Norwegian Bokmål" lang="nb" hreflang="nb" data-title="Endelig tilstandsmaskin" data-language-autonym="Norsk bokmål" data-language-local-name="Norwegian Bokmål" class="interlanguage-link-target"><span>Norsk bokmål</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Automat_sko%C5%84czony" title="Automat skończony – Polish" lang="pl" hreflang="pl" data-title="Automat skończony" data-language-autonym="Polski" data-language-local-name="Polish" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/M%C3%A1quina_de_estados_finita" title="Máquina de estados finita – Portuguese" lang="pt" hreflang="pt" data-title="Máquina de estados finita" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ro mw-list-item"><a href="https://ro.wikipedia.org/wiki/Automat_finit" title="Automat finit – Romanian" lang="ro" hreflang="ro" data-title="Automat finit" data-language-autonym="Română" data-language-local-name="Romanian" class="interlanguage-link-target"><span>Română</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82" title="Конечный автомат – Russian" lang="ru" hreflang="ru" data-title="Конечный автомат" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sk mw-list-item"><a href="https://sk.wikipedia.org/wiki/Kone%C4%8Dn%C3%BD_automat" title="Konečný automat – Slovak" lang="sk" hreflang="sk" data-title="Konečný automat" data-language-autonym="Slovenčina" data-language-local-name="Slovak" class="interlanguage-link-target"><span>Slovenčina</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BD%D0%B0%D1%87%D0%B0%D0%BD_%D0%B0%D1%83%D1%82%D0%BE%D0%BC%D0%B0%D1%82" title="Коначан аутомат – Serbian" lang="sr" hreflang="sr" data-title="Коначан аутомат" data-language-autonym="Српски / srpski" data-language-local-name="Serbian" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-sh mw-list-item"><a href="https://sh.wikipedia.org/wiki/Kona%C4%8Dni_automat" title="Konačni automat – Serbo-Croatian" lang="sh" hreflang="sh" data-title="Konačni automat" data-language-autonym="Srpskohrvatski / српскохрватски" data-language-local-name="Serbo-Croatian" class="interlanguage-link-target"><span>Srpskohrvatski / српскохрватски</span></a></li><li class="interlanguage-link interwiki-fi mw-list-item"><a href="https://fi.wikipedia.org/wiki/%C3%84%C3%A4rellinen_automaatti" title="Äärellinen automaatti – Finnish" lang="fi" hreflang="fi" data-title="Äärellinen automaatti" data-language-autonym="Suomi" data-language-local-name="Finnish" class="interlanguage-link-target"><span>Suomi</span></a></li><li class="interlanguage-link interwiki-sv mw-list-item"><a href="https://sv.wikipedia.org/wiki/%C3%84ndlig_automat" title="Ändlig automat – Swedish" lang="sv" hreflang="sv" data-title="Ändlig automat" data-language-autonym="Svenska" data-language-local-name="Swedish" class="interlanguage-link-target"><span>Svenska</span></a></li><li class="interlanguage-link interwiki-th mw-list-item"><a href="https://th.wikipedia.org/wiki/%E0%B9%80%E0%B8%84%E0%B8%A3%E0%B8%B7%E0%B9%88%E0%B8%AD%E0%B8%87%E0%B8%AA%E0%B8%96%E0%B8%B2%E0%B8%99%E0%B8%B0%E0%B8%88%E0%B8%B3%E0%B8%81%E0%B8%B1%E0%B8%94" title="เครื่องสถานะจำกัด – Thai" lang="th" hreflang="th" data-title="เครื่องสถานะจำกัด" data-language-autonym="ไทย" data-language-local-name="Thai" class="interlanguage-link-target"><span>ไทย</span></a></li><li class="interlanguage-link interwiki-tr mw-list-item"><a href="https://tr.wikipedia.org/wiki/Sonlu_durum_makinesi" title="Sonlu durum makinesi – Turkish" lang="tr" hreflang="tr" data-title="Sonlu durum makinesi" data-language-autonym="Türkçe" data-language-local-name="Turkish" class="interlanguage-link-target"><span>Türkçe</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%A1%D0%BA%D1%96%D0%BD%D1%87%D0%B5%D0%BD%D0%BD%D0%B8%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82" title="Скінченний автомат – Ukrainian" lang="uk" hreflang="uk" data-title="Скінченний автомат" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-vi mw-list-item"><a href="https://vi.wikipedia.org/wiki/M%C3%A1y_tr%E1%BA%A1ng_th%C3%A1i_h%E1%BB%AFu_h%E1%BA%A1n" title="Máy trạng thái hữu hạn – Vietnamese" lang="vi" hreflang="vi" data-title="Máy trạng thái hữu hạn" data-language-autonym="Tiếng Việt" data-language-local-name="Vietnamese" class="interlanguage-link-target"><span>Tiếng Việt</span></a></li><li class="interlanguage-link interwiki-zh-yue mw-list-item"><a href="https://zh-yue.wikipedia.org/wiki/%E6%9C%89%E9%99%90%E7%8B%80%E6%85%8B%E6%A9%9F" title="有限狀態機 – Cantonese" lang="yue" hreflang="yue" data-title="有限狀態機" data-language-autonym="粵語" data-language-local-name="Cantonese" class="interlanguage-link-target"><span>粵語</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E6%9C%89%E9%99%90%E7%8A%B6%E6%80%81%E6%9C%BA" title="有限状态机 – Chinese" lang="zh" hreflang="zh" data-title="有限状态机" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q176452#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Finite-state_machine" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Finite-state_machine" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Finite-state_machine"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Finite-state_machine&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Finite-state_machine&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Finite-state_machine"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Finite-state_machine&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Finite-state_machine&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Finite-state_machine" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Finite-state_machine" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Finite-state_machine&oldid=1246478939" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Finite-state_machine&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Finite-state_machine&id=1246478939&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FFinite-state_machine"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FFinite-state_machine"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Finite-state_machine&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Finite-state_machine&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:Finite_state_machine" hreflang="en"><span>Wikimedia Commons</span></a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q176452" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Mathematical model of computation</div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">"State machine" redirects here. For infinite-state machines, see <a href="/wiki/Transition_system" title="Transition system">Transition system</a>. For fault-tolerance methodology, see <a href="/wiki/State_machine_replication" title="State machine replication">State machine replication</a>.</div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">"SFSM" redirects here. For the Italian railway company, see <a href="/wiki/Circumvesuviana" title="Circumvesuviana">Circumvesuviana</a>.</div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">"Finite automata" redirects here. For the electro-industrial group, see <a href="/wiki/Finite_Automata_(band)" title="Finite Automata (band)">Finite Automata (band)</a>.</div> <p class="mw-empty-elt"> </p> <div class="thumb tright" style=""><div class="thumbinner" style="width:302px"><div class="thumbimage noresize" style="width:300px;"> <figure class="noresize mw-ext-imagemap-desc-top-right" typeof="mw:File"><span><img src="//upload.wikimedia.org/wikipedia/commons/thumb/a/a2/Automata_theory.svg/300px-Automata_theory.svg.png" decoding="async" width="300" height="225" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/a2/Automata_theory.svg/450px-Automata_theory.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/a2/Automata_theory.svg/600px-Automata_theory.svg.png 2x" data-file-width="800" data-file-height="600" usemap="#ImageMap_f881d23f9d31905a" resource="/wiki/File:Automata_theory.svg" /></span><map name="ImageMap_f881d23f9d31905a"><area href="/wiki/Combinational_logic" shape="rect" coords="101,75,255,124" alt="Combinational logic" title="Combinational logic" /><area href="/wiki/Finite-state_machine" shape="rect" coords="71,68,266,154" alt="Finite-state machine" title="Finite-state machine" /><area href="/wiki/Pushdown_automaton" shape="rect" coords="41,60,278,184" alt="Pushdown automaton" title="Pushdown automaton" /><area href="/wiki/Turing_machine" shape="rect" coords="11,53,289,214" alt="Turing machine" title="Turing machine" /><area href="/wiki/Automata_theory" shape="rect" coords="4,4,296,49" alt="Automata theory" title="Automata theory" /></map><figcaption></figcaption></figure></div><div class="thumbcaption">Classes of automata <div class="noprint"><span style="font-size:85%;">(Clicking on each layer gets an article on that subject)</span></div></div></div></div> <p>A <b>finite-state machine</b> (<b>FSM</b>) or <b>finite-state automaton</b> (<b>FSA</b>, plural: <i>automata</i>), <b>finite automaton</b>, or simply a <b>state machine</b>, is a mathematical <a href="/wiki/Model_of_computation" title="Model of computation">model of computation</a>. It is an <a href="/wiki/Abstract_machine" title="Abstract machine">abstract machine</a> that can be in exactly one of a finite number of <i><a href="/wiki/State_(computer_science)" title="State (computer science)">states</a></i> at any given time. The FSM can change from one state to another in response to some <a href="/wiki/Input_(computer_science)" title="Input (computer science)">inputs</a>; the change from one state to another is called a <i>transition</i>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition. Finite-state machines are of two types—<a href="/wiki/Deterministic_finite_automaton" title="Deterministic finite automaton">deterministic finite-state machines</a> and <a href="/wiki/Nondeterministic_finite_automaton" title="Nondeterministic finite automaton">non-deterministic finite-state machines</a>.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> For any non-deterministic finite-state machine, an equivalent deterministic one can be constructed. </p><p>The behavior of state machines can be observed in many devices in modern society that perform a predetermined sequence of actions depending on a sequence of events with which they are presented. Simple examples are: <a href="/wiki/Vending_machine" title="Vending machine">vending machines</a>, which dispense products when the proper combination of coins is deposited; <a href="/wiki/Elevator" title="Elevator">elevators</a>, whose sequence of stops is determined by the floors requested by riders; <a href="/wiki/Traffic_light" title="Traffic light">traffic lights</a>, which change sequence when cars are waiting; <a href="/wiki/Combination_lock" title="Combination lock">combination locks</a>, which require the input of a sequence of numbers in the proper order. </p><p>The finite-state machine has less computational power than some other models of computation such as the <a href="/wiki/Turing_machine" title="Turing machine">Turing machine</a>.<sup id="cite_ref-Belzer_3-0" class="reference"><a href="#cite_note-Belzer-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> The computational power distinction means there are computational tasks that a Turing machine can do but an FSM cannot. This is because an FSM's <a href="/wiki/Computer_memory" title="Computer memory">memory</a> is limited by the number of states it has. A finite-state machine has the same computational power as a Turing machine that is restricted such that its head may only perform "read" operations, and always has to move from left to right. FSMs are studied in the more general field of <a href="/wiki/Automata_theory" title="Automata theory">automata theory</a>. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Example:_coin-operated_turnstile">Example: coin-operated turnstile</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=1" title="Edit section: Example: coin-operated turnstile"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Turnstile_state_machine_colored.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/9/9e/Turnstile_state_machine_colored.svg/330px-Turnstile_state_machine_colored.svg.png" decoding="async" width="330" height="143" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/9/9e/Turnstile_state_machine_colored.svg/495px-Turnstile_state_machine_colored.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/9/9e/Turnstile_state_machine_colored.svg/660px-Turnstile_state_machine_colored.svg.png 2x" data-file-width="790" data-file-height="343" /></a><figcaption>State diagram for a turnstile</figcaption></figure> <figure typeof="mw:File/Thumb"><a href="/wiki/File:Tornelli.jpg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/f/f2/Tornelli.jpg/159px-Tornelli.jpg" decoding="async" width="159" height="200" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/f/f2/Tornelli.jpg/239px-Tornelli.jpg 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/f/f2/Tornelli.jpg/319px-Tornelli.jpg 2x" data-file-width="600" data-file-height="752" /></a><figcaption>A turnstile</figcaption></figure> <p>An example of a simple mechanism that can be modeled by a state machine is a <a href="/wiki/Turnstile" title="Turnstile">turnstile</a>.<sup id="cite_ref-Koshy_4-0" class="reference"><a href="#cite_note-Koshy-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-⁇⁇⁇?_5-0" class="reference"><a href="#cite_note-⁇⁇⁇?-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> A turnstile, used to control access to subways and amusement park rides, is a gate with three rotating arms at waist height, one across the entryway. Initially the arms are locked, blocking the entry, preventing patrons from passing through. Depositing a coin or <a href="/wiki/Token_coin" title="Token coin">token</a> in a slot on the turnstile unlocks the arms, allowing a single customer to push through. After the customer passes through, the arms are locked again until another coin is inserted. </p><p>Considered as a state machine, the turnstile has two possible states: <i>Locked</i> and <i>Unlocked</i>.<sup id="cite_ref-Koshy_4-1" class="reference"><a href="#cite_note-Koshy-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> There are two possible inputs that affect its state: putting a coin in the slot (<i>coin</i>) and pushing the arm (<i>push</i>). In the locked state, pushing on the arm has no effect; no matter how many times the input <i>push</i> is given, it stays in the locked state. Putting a coin in – that is, giving the machine a <i>coin</i> input – shifts the state from <i>Locked</i> to <i>Unlocked</i>. In the unlocked state, putting additional coins in has no effect; that is, giving additional <i>coin</i> inputs does not change the state. A customer pushing through the arms gives a <i>push</i> input and resets the state to <i>Locked</i>. </p><p>The turnstile state machine can be represented by a <a href="/wiki/State-transition_table" title="State-transition table">state-transition table</a>, showing for each possible state, the transitions between them (based upon the inputs given to the machine) and the outputs resulting from each input: </p> <dl><dd><dl><dd><table class="wikitable"> <tbody><tr> <th>Current State </th> <th>Input </th> <th>Next State </th> <th>Output </th></tr> <tr> <th rowspan="2">Locked </th> <td>coin</td> <td>Unlocked</td> <td>Unlocks the turnstile so that the customer can push through. </td></tr> <tr> <td>push</td> <td>Locked</td> <td>None </td></tr> <tr> <th rowspan="2">Unlocked </th> <td>coin</td> <td>Unlocked</td> <td>None </td></tr> <tr> <td>push</td> <td>Locked</td> <td>When the customer has pushed through, locks the turnstile. </td></tr></tbody></table></dd></dl></dd></dl> <p>The turnstile state machine can also be represented by a <a href="/wiki/Directed_graph" title="Directed graph">directed graph</a> called a <a href="/wiki/State_diagram" title="State diagram">state diagram</a> <i>(above)</i>. Each state is represented by a <a href="/wiki/Node_(graph_theory)" class="mw-redirect" title="Node (graph theory)">node</a> (<i>circle</i>). Edges (<i>arrows</i>) show the transitions from one state to another. Each arrow is labeled with the input that triggers that transition. An input that doesn't cause a change of state (such as a <i>coin</i> input in the <i>Unlocked</i> state) is represented by a circular arrow returning to the original state. The arrow into the <i>Locked</i> node from the black dot indicates it is the initial state. </p> <div class="mw-heading mw-heading2"><h2 id="Concepts_and_terminology">Concepts and terminology</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=2" title="Edit section: Concepts and terminology"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A <i>state</i> is a description of the status of a system that is waiting to execute a <i>transition</i>. A transition is a set of actions to be executed when a condition is fulfilled or when an event is received. For example, when using an audio system to listen to the radio (the system is in the "radio" state), receiving a "next" stimulus results in moving to the next station. When the system is in the "CD" state, the "next" stimulus results in moving to the next track. Identical stimuli trigger different actions depending on the current state. </p><p>In some finite-state machine representations, it is also possible to associate actions with a state: </p> <ul><li>an entry action: performed <i>when entering</i> the state, and</li> <li>an exit action: performed <i>when exiting</i> the state.</li></ul> <div class="mw-heading mw-heading2"><h2 id="Representations">Representations</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=3" title="Edit section: Representations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:UML_state_machine_Fig5.png" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/2/20/UML_state_machine_Fig5.png/220px-UML_state_machine_Fig5.png" decoding="async" width="220" height="87" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/2/20/UML_state_machine_Fig5.png/330px-UML_state_machine_Fig5.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/2/20/UML_state_machine_Fig5.png/440px-UML_state_machine_Fig5.png 2x" data-file-width="743" data-file-height="295" /></a><figcaption>Fig. 1 UML state chart example (a toaster oven)</figcaption></figure> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:SdlStateMachine.png" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/3/38/SdlStateMachine.png/220px-SdlStateMachine.png" decoding="async" width="220" height="298" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/3/38/SdlStateMachine.png/330px-SdlStateMachine.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/3/38/SdlStateMachine.png/440px-SdlStateMachine.png 2x" data-file-width="539" data-file-height="729" /></a><figcaption>Fig. 2 SDL state machine example</figcaption></figure> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Finite_state_machine_example_with_comments.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Finite_state_machine_example_with_comments.svg/220px-Finite_state_machine_example_with_comments.svg.png" decoding="async" width="220" height="293" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Finite_state_machine_example_with_comments.svg/330px-Finite_state_machine_example_with_comments.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Finite_state_machine_example_with_comments.svg/440px-Finite_state_machine_example_with_comments.svg.png 2x" data-file-width="420" data-file-height="560" /></a><figcaption>Fig. 3 Example of a simple finite-state machine</figcaption></figure> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">For an introduction, see <a href="/wiki/State_diagram" title="State diagram">State diagram</a>.</div> <div class="mw-heading mw-heading3"><h3 id="State/Event_table"><span id="State.2FEvent_table"></span>State/Event table</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=4" title="Edit section: State/Event table"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Several <a href="/wiki/State-transition_table" title="State-transition table">state-transition table</a> types are used. The most common representation is shown below: the combination of current state (e.g. B) and input (e.g. Y) shows the next state (e.g. C). The complete action's information is not directly described in the table and can only be added using footnotes.<sup class="noprint Inline-Template" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Please_clarify" title="Wikipedia:Please clarify"><span title="The text near this tag needs further explanation. (March 2021)">further explanation needed</span></a></i>]</sup> An FSM definition including the full action's information is possible using <a href="/wiki/Virtual_finite_state_machine#State_Table" class="mw-redirect" title="Virtual finite state machine">state tables</a> (see also <a href="/wiki/Virtual_finite-state_machine" title="Virtual finite-state machine">virtual finite-state machine</a>). </p> <table class="wikitable" style="text-align:center; margin-left:auto; margin-right:auto;"> <caption>State-transition table </caption> <tbody><tr> <th style="background:#EAECF0;background:linear-gradient(to top right,#EAECF0 49%,#AAA 49.5%,#AAA 50.5%,#EAECF0 51%);line-height:1.2;padding:0.1em 0.4em;"><div style="margin-left:2em;text-align:right">  Current<br />state</div><div style="margin-right:2em;text-align:left">Input</div></th> <th>State A</th> <th>State B</th> <th>State C </th></tr> <tr> <th>Input X </th> <td>...</td> <td>...</td> <td>... </td></tr> <tr> <th>Input Y </th> <td>...</td> <td>State C</td> <td>... </td></tr> <tr> <th>Input Z </th> <td>...</td> <td>...</td> <td>... </td></tr></tbody></table> <div class="mw-heading mw-heading3"><h3 id="UML_state_machines">UML state machines</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=5" title="Edit section: UML state machines"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The <a href="/wiki/Unified_Modeling_Language" title="Unified Modeling Language">Unified Modeling Language</a> has a notation for describing state machines. <a href="/wiki/UML_state_machine" title="UML state machine">UML state machines</a> overcome the limitations<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (March 2021)">citation needed</span></a></i>]</sup> of traditional finite-state machines while retaining their main benefits. UML state machines introduce the new concepts of <a href="/wiki/UML_state_machine#Hierarchically_nested_states" title="UML state machine">hierarchically nested states</a> and <a href="/wiki/UML_state_machine#Orthogonal_regions" title="UML state machine">orthogonal regions</a>, while extending the notion of <a href="/wiki/UML_state_machine#Actions_and_transitions" title="UML state machine">actions</a>. UML state machines have the characteristics of both <a href="/wiki/Mealy_machine" title="Mealy machine">Mealy machines</a> and <a href="/wiki/Moore_machine" title="Moore machine">Moore machines</a>. They support <a href="/wiki/UML_state_machine#Actions_and_transitions" title="UML state machine">actions</a> that depend on both the state of the system and the triggering <a href="/wiki/UML_state_machine#Events" title="UML state machine">event</a>, as in Mealy machines, as well as <a href="/wiki/UML_state_machine#Entry_and_exit_actions" title="UML state machine">entry and exit actions</a>, which are associated with states rather than transitions, as in Moore machines.<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (January 2017)">citation needed</span></a></i>]</sup> </p> <div class="mw-heading mw-heading3"><h3 id="SDL_state_machines">SDL state machines</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=6" title="Edit section: SDL state machines"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The <a href="/wiki/Specification_and_Description_Language" title="Specification and Description Language">Specification and Description Language</a> is a standard from <a href="/wiki/ITU" class="mw-redirect" title="ITU">ITU</a> that includes graphical symbols to describe actions in the transition: </p> <ul><li>send an event</li> <li>receive an event</li> <li>start a timer</li> <li>cancel a timer</li> <li>start another concurrent state machine</li> <li>decision</li></ul> <p>SDL embeds basic data types called "Abstract Data Types", an action language, and an execution semantic in order to make the finite-state machine executable.<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (January 2017)">citation needed</span></a></i>]</sup> </p> <div class="mw-heading mw-heading3"><h3 id="Other_state_diagrams">Other state diagrams</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=7" title="Edit section: Other state diagrams"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>There are a large number of variants to represent an FSM such as the one in figure 3. </p> <div class="mw-heading mw-heading2"><h2 id="Usage">Usage</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=8" title="Edit section: Usage"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In addition to their use in modeling reactive systems presented here, finite-state machines are significant in many different areas, including <a href="/wiki/Electrical_engineering" title="Electrical engineering">electrical engineering</a>, <a href="/wiki/Linguistics" title="Linguistics">linguistics</a>, <a href="/wiki/Computer_science" title="Computer science">computer science</a>, <a href="/wiki/Philosophy" title="Philosophy">philosophy</a>, <a href="/wiki/Biology" title="Biology">biology</a>, <a href="/wiki/Mathematic" class="mw-redirect" title="Mathematic">mathematics</a>, <a href="/wiki/Video_game_programming" title="Video game programming">video game programming</a>, and <a href="/wiki/Logic" title="Logic">logic</a>. Finite-state machines are a class of automata studied in <a href="/wiki/Automata_theory" title="Automata theory">automata theory</a> and the <a href="/wiki/Theory_of_computation" title="Theory of computation">theory of computation</a>. In computer science, finite-state machines are widely used in modeling of application behavior (<a href="/wiki/Control_theory" title="Control theory">control theory</a>), design of <a href="/wiki/Digital_electronics" title="Digital electronics">hardware digital systems</a>, <a href="/wiki/Software_engineering" title="Software engineering">software engineering</a>, <a href="/wiki/Compiler" title="Compiler">compilers</a>, <a href="/wiki/Network_protocol" class="mw-redirect" title="Network protocol">network protocols</a>, and <a href="/wiki/Computational_linguistics" title="Computational linguistics">computational linguistics</a>. </p> <div class="mw-heading mw-heading2"><h2 id="Classification">Classification</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=9" title="Edit section: Classification"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Finite-state machines can be subdivided into acceptors, classifiers, transducers and sequencers.<sup id="cite_ref-Keller2001_6-0" class="reference"><a href="#cite_note-Keller2001-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Acceptors">Acceptors</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=10" title="Edit section: Acceptors"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Fsm_parsing_word_nice.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/a/a8/Fsm_parsing_word_nice.svg/220px-Fsm_parsing_word_nice.svg.png" decoding="async" width="220" height="128" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/a8/Fsm_parsing_word_nice.svg/330px-Fsm_parsing_word_nice.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/a8/Fsm_parsing_word_nice.svg/440px-Fsm_parsing_word_nice.svg.png 2x" data-file-width="606" data-file-height="353" /></a><figcaption>Fig. 4: Acceptor FSM: parsing the string "nice".</figcaption></figure> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:DFAexample.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/9/9d/DFAexample.svg/220px-DFAexample.svg.png" decoding="async" width="220" height="132" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/9/9d/DFAexample.svg/330px-DFAexample.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/9/9d/DFAexample.svg/440px-DFAexample.svg.png 2x" data-file-width="500" data-file-height="299" /></a><figcaption>Fig. 5: Representation of an acceptor; this example shows one that determines whether a binary number has an even number of 0s, where <i>S</i><sub>1</sub> is an <i>accepting state</i> and <i>S</i><sub>2</sub> is a <i>non accepting state</i>.</figcaption></figure> <p><b>Acceptors</b> (also called <i>detectors</i> or <b>recognizers</b>) produce binary output, indicating whether or not the received input is accepted. Each state of an acceptor is either <i>accepting</i> or <i>non accepting</i>. Once all input has been received, if the current state is an accepting state, the input is accepted; otherwise it is rejected. As a rule, input is a <a href="/wiki/String_(computer_science)" title="String (computer science)">sequence of symbols</a> (characters); actions are not used. The start state can also be an accepting state, in which case the acceptor accepts the empty string. The example in figure 4 shows an acceptor that accepts the string "nice". In this acceptor, the only accepting state is state 7. </p><p>A (possibly infinite) set of symbol sequences, called a <a href="/wiki/Formal_language" title="Formal language">formal language</a>, is a <a href="/wiki/Regular_language" title="Regular language">regular language</a> if there is some acceptor that accepts <i>exactly</i> that set. For example, the set of binary strings with an even number of zeroes is a regular language (cf. Fig. 5), while the set of all strings whose length is a prime number is not.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page / location: 18, 71">: 18, 71 </span></sup> </p><p>An acceptor could also be described as defining a language that would contain every string accepted by the acceptor but none of the rejected ones; that language is <i>accepted</i> by the acceptor. By definition, the languages accepted by acceptors are the <a href="/wiki/Regular_language" title="Regular language">regular languages</a>. </p><p>The problem of determining the language accepted by a given acceptor is an instance of the <a href="/wiki/Algebraic_path_problem" class="mw-redirect" title="Algebraic path problem">algebraic path problem</a>—itself a generalization of the <a href="/wiki/Shortest_path_problem" title="Shortest path problem">shortest path problem</a> to graphs with edges weighted by the elements of an (arbitrary) <a href="/wiki/Semiring" title="Semiring">semiring</a>.<sup id="cite_ref-PoulyKohlas2012_8-0" class="reference"><a href="#cite_note-PoulyKohlas2012-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup><sup class="noprint Inline-Template" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Manual_of_Style#Technical_language" title="Wikipedia:Manual of Style"><span title="The material near this tag may be using jargon that limits the article's accessibility. (January 2017)">jargon</span></a></i>]</sup> </p><p>An example of an accepting state appears in Fig. 5: a <a href="/wiki/Deterministic_finite_automaton" title="Deterministic finite automaton">deterministic finite automaton</a> (DFA) that detects whether the <a href="/wiki/Binary_numeral_system" class="mw-redirect" title="Binary numeral system">binary</a> input string contains an even number of 0s. </p><p><i>S</i><sub>1</sub> (which is also the start state) indicates the state at which an even number of 0s has been input. S<sub>1</sub> is therefore an accepting state. This acceptor will finish in an accept state, if the binary string contains an even number of 0s (including any binary string containing no 0s). Examples of strings accepted by this acceptor are <a href="/wiki/%CE%95" class="mw-redirect" title="Ε">ε</a> (the <a href="/wiki/Empty_string" title="Empty string">empty string</a>), 1, 11, 11..., 00, 010, 1010, 10110, etc. </p> <div class="mw-heading mw-heading3"><h3 id="Classifiers">Classifiers</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=11" title="Edit section: Classifiers"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><b>Classifiers</b> are a generalization of acceptors that produce <i>n</i>-ary output where <i>n</i> is strictly greater than two.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Transducers">Transducers</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=12" title="Edit section: Transducers"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/Finite-state_transducer" title="Finite-state transducer">Finite-state transducer</a></div> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Fsm_Moore_model_door_control.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/7/71/Fsm_Moore_model_door_control.svg/220px-Fsm_Moore_model_door_control.svg.png" decoding="async" width="220" height="222" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/71/Fsm_Moore_model_door_control.svg/330px-Fsm_Moore_model_door_control.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/71/Fsm_Moore_model_door_control.svg/440px-Fsm_Moore_model_door_control.svg.png 2x" data-file-width="512" data-file-height="517" /></a><figcaption>Fig. 6 Transducer FSM: Moore model example</figcaption></figure> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Fsm_mealy_model_door_control.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/7/72/Fsm_mealy_model_door_control.svg/220px-Fsm_mealy_model_door_control.svg.png" decoding="async" width="220" height="73" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/72/Fsm_mealy_model_door_control.svg/330px-Fsm_mealy_model_door_control.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/72/Fsm_mealy_model_door_control.svg/440px-Fsm_mealy_model_door_control.svg.png 2x" data-file-width="512" data-file-height="171" /></a><figcaption>Fig. 7 Transducer FSM: Mealy model example</figcaption></figure> <p><i>Transducers</i> produce output based on a given input and/or a state using actions. They are used for control applications and in the field of <a href="/wiki/Computational_linguistics" title="Computational linguistics">computational linguistics</a>. </p><p>In control applications, two types are distinguished: </p> <dl><dt><a href="/wiki/Moore_machine" title="Moore machine">Moore machine</a></dt> <dd>The FSM uses only entry actions, i.e., output depends only on state. The advantage of the Moore model is a simplification of the behaviour. Consider an elevator door. The state machine recognizes two commands: "command_open" and "command_close", which trigger state changes. The entry action (E:) in state "Opening" starts a motor opening the door, the entry action in state "Closing" starts a motor in the other direction closing the door. States "Opened" and "Closed" stop the motor when fully opened or closed. They signal to the outside world (e.g., to other state machines) the situation: "door is open" or "door is closed".</dd></dl> <dl><dt><a href="/wiki/Mealy_machine" title="Mealy machine">Mealy machine</a></dt> <dd>The FSM also uses input actions, i.e., output depends on input and state. The use of a Mealy FSM leads often to a reduction of the number of states. The example in figure 7 shows a Mealy FSM implementing the same behaviour as in the Moore example (the behaviour depends on the implemented FSM execution model and will work, e.g., for <a href="/wiki/Virtual_finite-state_machine" title="Virtual finite-state machine">virtual FSM</a> but not for <a href="/wiki/Event-driven_finite-state_machine" title="Event-driven finite-state machine">event-driven FSM</a>). There are two input actions (I:): "start motor to close the door if command_close arrives" and "start motor in the other direction to open the door if command_open arrives". The "opening" and "closing" intermediate states are not shown.</dd></dl> <div class="mw-heading mw-heading3"><h3 id="Sequencers">Sequencers</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=13" title="Edit section: Sequencers"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><i>Sequencers</i> (also called <i>generators</i>) are a subclass of acceptors and transducers that have a single-letter input alphabet. They produce only one sequence, which can be seen as an output sequence of acceptor or transducer outputs.<sup id="cite_ref-Keller2001_6-1" class="reference"><a href="#cite_note-Keller2001-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Determinism">Determinism</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=14" title="Edit section: Determinism"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A further distinction is between <i>deterministic</i> (<a href="/wiki/Deterministic_finite_automaton" title="Deterministic finite automaton">DFA</a>) and <i>non-deterministic</i> (<a href="/wiki/Nondeterministic_finite_automaton" title="Nondeterministic finite automaton">NFA</a>, <a href="/wiki/Generalized_nondeterministic_finite_automaton" title="Generalized nondeterministic finite automaton">GNFA</a>) automata. In a deterministic automaton, every state has exactly one transition for each possible input. In a non-deterministic automaton, an input can lead to one, more than one, or no transition for a given state. The <a href="/wiki/Powerset_construction" title="Powerset construction">powerset construction</a> algorithm can transform any nondeterministic automaton into a (usually more complex) deterministic automaton with identical functionality. </p><p>A finite-state machine with only one state is called a "combinatorial FSM". It only allows actions upon transition <i>into</i> a state. This concept is useful in cases where a number of finite-state machines are required to work together, and when it is convenient to consider a purely combinatorial part as a form of FSM to suit the design tools.<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Alternative_semantics">Alternative semantics</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=15" title="Edit section: Alternative semantics"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>There are other sets of semantics available to represent state machines. For example, there are tools for modeling and designing logic for embedded controllers.<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> They combine <a href="/wiki/UML_state_machine#Hierarchically_nested_states" title="UML state machine">hierarchical state machines</a> (which usually have more than one current state), flow graphs, and <a href="/wiki/Truth_table" title="Truth table">truth tables</a> into one language, resulting in a different formalism and set of semantics.<sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> These charts, like <a href="/wiki/David_Harel" title="David Harel">Harel's</a> original state machines,<sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> support hierarchically nested states, <a href="/wiki/UML_state_machine#Orthogonal_regions" title="UML state machine">orthogonal regions</a>, state actions, and transition actions.<sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Mathematical_model">Mathematical model</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=16" title="Edit section: Mathematical model"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In accordance with the general classification, the following formal definitions are found. </p><p>A <i>deterministic finite-state machine</i> or <i>deterministic finite-state acceptor</i> is a <a href="/wiki/Tuple" title="Tuple">quintuple</a> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\Sigma ,S,s_{0},\delta ,F)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi mathvariant="normal">Σ</mi> <mo>,</mo> <mi>S</mi> <mo>,</mo> <msub> <mi>s</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>,</mo> <mi>δ</mi> <mo>,</mo> <mi>F</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\Sigma ,S,s_{0},\delta ,F)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/aae5816b47a1d60ad6c3aa775f0e012fe89edddc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.056ex; height:2.843ex;" alt="{\displaystyle (\Sigma ,S,s_{0},\delta ,F)}"></span>, where: </p> <ul><li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">Σ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9e1f558f53cda207614abdf90162266c70bc5c1e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }"></span> is the input <a href="/wiki/Alphabet_(computer_science)" class="mw-redirect" title="Alphabet (computer science)">alphabet</a> (a finite non-empty set of symbols);</li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}"></span> is a finite non-empty set of states;</li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{0}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>s</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle s_{0}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/25c32f35eb134d23b3c45f1c878d59b0a112ede4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.145ex; height:2.009ex;" alt="{\displaystyle s_{0}}"></span> is an initial state, an element of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}"></span>;</li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>δ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \delta }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c5321cfa797202b3e1f8620663ff43c4660ea03a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:2.343ex;" alt="{\displaystyle \delta }"></span> is the state-transition function: <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta :S\times \Sigma \rightarrow S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>δ</mi> <mo>:</mo> <mi>S</mi> <mo>×</mo> <mi mathvariant="normal">Σ</mi> <mo stretchy="false">→</mo> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \delta :S\times \Sigma \rightarrow S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/65f6cb1ecf4bb5f8a7e72ed569561934475a3d45" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:14.117ex; height:2.343ex;" alt="{\displaystyle \delta :S\times \Sigma \rightarrow S}"></span> (in a <a href="/wiki/Nondeterministic_finite_automaton" title="Nondeterministic finite automaton">nondeterministic finite automaton</a> it would be <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta :S\times \Sigma \rightarrow {\mathcal {P}}(S)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>δ</mi> <mo>:</mo> <mi>S</mi> <mo>×</mo> <mi mathvariant="normal">Σ</mi> <mo stretchy="false">→</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic" mathvariant="script">P</mi> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>S</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \delta :S\times \Sigma \rightarrow {\mathcal {P}}(S)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6be8ca71c32967d004a7412e6d2ce7df6bd2a422" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.63ex; height:2.843ex;" alt="{\displaystyle \delta :S\times \Sigma \rightarrow {\mathcal {P}}(S)}"></span>, i.e. <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>δ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \delta }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c5321cfa797202b3e1f8620663ff43c4660ea03a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:2.343ex;" alt="{\displaystyle \delta }"></span> would return a set of states);</li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>F</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle F}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/545fd099af8541605f7ee55f08225526be88ce57" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.741ex; height:2.176ex;" alt="{\displaystyle F}"></span> is the set of final states, a (possibly empty) subset of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}"></span>.</li></ul> <p>For both deterministic and non-deterministic FSMs, it is conventional to allow <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>δ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \delta }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c5321cfa797202b3e1f8620663ff43c4660ea03a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:2.343ex;" alt="{\displaystyle \delta }"></span> to be a <a href="/wiki/Partial_function" title="Partial function">partial function</a>, i.e. <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta (s,x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>δ</mi> <mo stretchy="false">(</mo> <mi>s</mi> <mo>,</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \delta (s,x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e324f93387aa29a0243f13fc75d5f35bd09bcc9f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.312ex; height:2.843ex;" alt="{\displaystyle \delta (s,x)}"></span> does not have to be defined for every combination of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s\in S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>s</mi> <mo>∈</mo> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle s\in S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/acce52dffd84d073a24f4606a175da60148fd0c6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.43ex; height:2.176ex;" alt="{\displaystyle s\in S}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in \Sigma }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>∈</mo> <mi mathvariant="normal">Σ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x\in \Sigma }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/af0a929ac30ea6c41ef08d5e6a6ca2309a97a695" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.848ex; height:2.176ex;" alt="{\displaystyle x\in \Sigma }"></span>. If an FSM <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>M</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle M}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}"></span> is in a state <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>s</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle s}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/01d131dfd7673938b947072a13a9744fe997e632" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}"></span>, the next symbol is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta (s,x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>δ</mi> <mo stretchy="false">(</mo> <mi>s</mi> <mo>,</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \delta (s,x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e324f93387aa29a0243f13fc75d5f35bd09bcc9f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.312ex; height:2.843ex;" alt="{\displaystyle \delta (s,x)}"></span> is not defined, then <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>M</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle M}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}"></span> can announce an error (i.e. reject the input). This is useful in definitions of general state machines, but less useful when transforming the machine. Some algorithms in their default form may require total functions. </p><p>A finite-state machine has the same computational power as a <a href="/wiki/Turing_machine" title="Turing machine">Turing machine</a> that is restricted such that its head may only perform "read" operations, and always has to move from left to right. That is, each formal language accepted by a finite-state machine is accepted by such a kind of restricted Turing machine, and vice versa.<sup id="cite_ref-16" class="reference"><a href="#cite_note-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup> </p><p>A <i><a href="/wiki/Finite-state_transducer" title="Finite-state transducer">finite-state transducer</a></i> is a <a href="/wiki/Sextuple" class="mw-redirect" title="Sextuple">sextuple</a> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\Sigma ,\Gamma ,S,s_{0},\delta ,\omega )}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi mathvariant="normal">Σ</mi> <mo>,</mo> <mi mathvariant="normal">Γ</mi> <mo>,</mo> <mi>S</mi> <mo>,</mo> <msub> <mi>s</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>,</mo> <mi>δ</mi> <mo>,</mo> <mi>ω</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\Sigma ,\Gamma ,S,s_{0},\delta ,\omega )}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2ee02696007a5569fbb05b2aefe534322db4ef03" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.248ex; height:2.843ex;" alt="{\displaystyle (\Sigma ,\Gamma ,S,s_{0},\delta ,\omega )}"></span>, where: </p> <ul><li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">Σ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9e1f558f53cda207614abdf90162266c70bc5c1e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }"></span> is the input <a href="/wiki/Alphabet_(computer_science)" class="mw-redirect" title="Alphabet (computer science)">alphabet</a> (a finite non-empty set of symbols);</li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Gamma }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">Γ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Gamma }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4cfde86a3f7ec967af9955d0988592f0693d2b19" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.453ex; height:2.176ex;" alt="{\displaystyle \Gamma }"></span> is the output alphabet (a finite non-empty set of symbols);</li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}"></span> is a finite non-empty set of states;</li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{0}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>s</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle s_{0}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/25c32f35eb134d23b3c45f1c878d59b0a112ede4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.145ex; height:2.009ex;" alt="{\displaystyle s_{0}}"></span> is the initial state, an element of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}"></span>;</li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>δ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \delta }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c5321cfa797202b3e1f8620663ff43c4660ea03a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:2.343ex;" alt="{\displaystyle \delta }"></span> is the state-transition function: <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta :S\times \Sigma \rightarrow S}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>δ</mi> <mo>:</mo> <mi>S</mi> <mo>×</mo> <mi mathvariant="normal">Σ</mi> <mo stretchy="false">→</mo> <mi>S</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \delta :S\times \Sigma \rightarrow S}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/65f6cb1ecf4bb5f8a7e72ed569561934475a3d45" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:14.117ex; height:2.343ex;" alt="{\displaystyle \delta :S\times \Sigma \rightarrow S}"></span>;</li> <li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \omega }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>ω</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \omega }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/48eff443f9de7a985bb94ca3bde20813ea737be8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.446ex; height:1.676ex;" alt="{\displaystyle \omega }"></span> is the output function.</li></ul> <p>If the output function depends on the state and input symbol (<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \omega :S\times \Sigma \rightarrow \Gamma }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>ω</mi> <mo>:</mo> <mi>S</mi> <mo>×</mo> <mi mathvariant="normal">Σ</mi> <mo stretchy="false">→</mo> <mi mathvariant="normal">Γ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \omega :S\times \Sigma \rightarrow \Gamma }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8a1714a8b284adc167cb480f1b1e4867ff366ca7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:14.468ex; height:2.176ex;" alt="{\displaystyle \omega :S\times \Sigma \rightarrow \Gamma }"></span>) that definition corresponds to the <i>Mealy model</i>, and can be modelled as a <a href="/wiki/Mealy_machine" title="Mealy machine">Mealy machine</a>. If the output function depends only on the state (<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \omega :S\rightarrow \Gamma }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>ω</mi> <mo>:</mo> <mi>S</mi> <mo stretchy="false">→</mo> <mi mathvariant="normal">Γ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \omega :S\rightarrow \Gamma }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/eea022d0f2030c0ff2f7728380d9786278d681db" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.949ex; height:2.176ex;" alt="{\displaystyle \omega :S\rightarrow \Gamma }"></span>) that definition corresponds to the <i>Moore model</i>, and can be modelled as a <a href="/wiki/Moore_machine" title="Moore machine">Moore machine</a>. A finite-state machine with no output function at all is known as a <a href="/wiki/Semiautomaton" title="Semiautomaton">semiautomaton</a> or <a href="/wiki/Transition_system" title="Transition system">transition system</a>. </p><p>If we disregard the first output symbol of a Moore machine, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \omega (s_{0})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>ω</mi> <mo stretchy="false">(</mo> <msub> <mi>s</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \omega (s_{0})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4ea353f7591f0dd332e3e2d47fa5a68b89f1e49f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.4ex; height:2.843ex;" alt="{\displaystyle \omega (s_{0})}"></span>, then it can be readily converted to an output-equivalent Mealy machine by setting the output function of every Mealy transition (i.e. labeling every edge) with the output symbol given of the destination Moore state. The converse transformation is less straightforward because a Mealy machine state may have different output labels on its incoming transitions (edges). Every such state needs to be split in multiple Moore machine states, one for every incident output symbol.<sup id="cite_ref-AndersonHead2006_17-0" class="reference"><a href="#cite_note-AndersonHead2006-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Optimization">Optimization</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=17" title="Edit section: Optimization"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/DFA_minimization" title="DFA minimization">DFA minimization</a></div> <p>Optimizing an FSM means finding a machine with the minimum number of states that performs the same function. The fastest known algorithm doing this is the <a href="/wiki/DFA_minimization#Hopcroft's_algorithm" title="DFA minimization">Hopcroft minimization algorithm</a>.<sup id="cite_ref-18" class="reference"><a href="#cite_note-18"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-19" class="reference"><a href="#cite_note-19"><span class="cite-bracket">[</span>19<span class="cite-bracket">]</span></a></sup> Other techniques include using an <a href="/wiki/Implication_table" title="Implication table">implication table</a>, or the Moore reduction procedure.<sup id="cite_ref-20" class="reference"><a href="#cite_note-20"><span class="cite-bracket">[</span>20<span class="cite-bracket">]</span></a></sup> Additionally, acyclic FSAs can be minimized in <a href="/wiki/Linear_time" class="mw-redirect" title="Linear time">linear time</a>.<sup id="cite_ref-21" class="reference"><a href="#cite_note-21"><span class="cite-bracket">[</span>21<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Implementation">Implementation</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=18" title="Edit section: Implementation"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Hardware_applications">Hardware applications</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=19" title="Edit section: Hardware applications"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:4_bit_counter.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/7/76/4_bit_counter.svg/220px-4_bit_counter.svg.png" decoding="async" width="220" height="117" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/76/4_bit_counter.svg/330px-4_bit_counter.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/76/4_bit_counter.svg/440px-4_bit_counter.svg.png 2x" data-file-width="1281" data-file-height="680" /></a><figcaption>Fig. 9 The <a href="/wiki/Circuit_diagram" title="Circuit diagram">circuit diagram</a> for a 4-bit <a href="/wiki/Transistor-transistor_logic" class="mw-redirect" title="Transistor-transistor logic">TTL</a> counter, a type of state machine</figcaption></figure> <p>In a <a href="/wiki/Digital_circuit" class="mw-redirect" title="Digital circuit">digital circuit</a>, an FSM may be built using a <a href="/wiki/Programmable_logic_device" title="Programmable logic device">programmable logic device</a>, a <a href="/wiki/Programmable_logic_controller" title="Programmable logic controller">programmable logic controller</a>, <a href="/wiki/Logic_gate" title="Logic gate">logic gates</a> and <a href="/wiki/Flip-flop_(electronics)" title="Flip-flop (electronics)">flip flops</a> or <a href="/wiki/Relay" title="Relay">relays</a>. More specifically, a hardware implementation requires a <a href="/wiki/Processor_register" title="Processor register">register</a> to store state variables, a block of <a href="/wiki/Combinational_logic" title="Combinational logic">combinational logic</a> 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 <a href="/wiki/Richards_controller" title="Richards controller">Richards controller</a>. </p><p>In a <i>Medvedev machine</i>, the output is directly connected to the state flip-flops minimizing the time delay between flip-flops and output.<sup id="cite_ref-22" class="reference"><a href="#cite_note-22"><span class="cite-bracket">[</span>22<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-23" class="reference"><a href="#cite_note-23"><span class="cite-bracket">[</span>23<span class="cite-bracket">]</span></a></sup> </p><p>Through <a href="/wiki/State_encoding_for_low_power" title="State encoding for low power">state encoding for low power</a> state machines may be optimized to minimize power consumption. </p> <div class="mw-heading mw-heading3"><h3 id="Software_applications">Software applications</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=20" title="Edit section: Software applications"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The following concepts are commonly used to build software applications with finite-state machines: </p> <ul><li><a href="/wiki/Automata-based_programming" title="Automata-based programming">Automata-based programming</a></li> <li><a href="/wiki/Event-driven_finite-state_machine" title="Event-driven finite-state machine">Event-driven finite-state machine</a></li> <li><a href="/wiki/Virtual_finite-state_machine" title="Virtual finite-state machine">Virtual finite-state machine</a></li> <li><a href="/wiki/State_pattern" title="State pattern">State design pattern</a></li></ul> <div class="mw-heading mw-heading3"><h3 id="Finite-state_machines_and_compilers">Finite-state machines and compilers</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=21" title="Edit section: Finite-state machines and compilers"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Finite automata are often used in the <a href="/wiki/Compilers#Front_end" class="mw-redirect" title="Compilers">frontend</a> of programming language compilers. Such a frontend may comprise several finite-state machines that implement a <a href="/wiki/Lexical_analysis" title="Lexical analysis">lexical analyzer</a> 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 <a href="/wiki/Context-free_grammar" title="Context-free grammar">context-free</a> parts of the programming language's grammar.<sup id="cite_ref-24" class="reference"><a href="#cite_note-24"><span class="cite-bracket">[</span>24<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=22" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1184024115">.mw-parser-output .div-col{margin-top:0.3em;column-width:30em}.mw-parser-output .div-col-small{font-size:90%}.mw-parser-output .div-col-rules{column-rule:1px solid #aaa}.mw-parser-output .div-col dl,.mw-parser-output .div-col ol,.mw-parser-output .div-col ul{margin-top:0}.mw-parser-output .div-col li,.mw-parser-output .div-col dd{page-break-inside:avoid;break-inside:avoid-column}</style><div class="div-col" style="column-width: 21em;"> <ul><li><a href="/wiki/Abstract_state_machine" title="Abstract state machine">Abstract state machines</a></li> <li><a href="/wiki/Alternating_finite_automaton" title="Alternating finite automaton">Alternating finite automaton</a></li> <li><a href="/wiki/Communicating_finite-state_machine" title="Communicating finite-state machine">Communicating finite-state machine</a></li> <li><a href="/wiki/Control_system" title="Control system">Control system</a></li> <li><a href="/wiki/Control_table" title="Control table">Control table</a></li> <li><a href="/wiki/Decision_table" title="Decision table">Decision tables</a></li> <li><a href="/wiki/DEVS" title="DEVS">DEVS</a></li> <li><a href="/wiki/Hidden_Markov_model" title="Hidden Markov model">Hidden Markov model</a></li> <li><a href="/wiki/Petri_net" title="Petri net">Petri net</a></li> <li><a href="/wiki/Pushdown_automaton" title="Pushdown automaton">Pushdown automaton</a></li> <li><a href="/wiki/Quantum_finite_automaton" title="Quantum finite automaton">Quantum finite automaton</a></li> <li><a href="/wiki/SCXML" title="SCXML">SCXML</a></li> <li><a href="/wiki/Semiautomaton" title="Semiautomaton">Semiautomaton</a></li> <li><a href="/wiki/Semigroup_action" title="Semigroup action">Semigroup action</a></li> <li><a href="/wiki/Sequential_logic" title="Sequential logic">Sequential logic</a></li> <li><a href="/wiki/State_diagram" title="State diagram">State diagram</a></li> <li><a href="/wiki/Synchronizing_word" title="Synchronizing word">Synchronizing word</a></li> <li><a href="/wiki/Transformation_semigroup" title="Transformation semigroup">Transformation semigroup</a></li> <li><a href="/wiki/Transition_system" title="Transition system">Transition system</a></li> <li><a href="/wiki/Tree_automaton" title="Tree automaton">Tree automaton</a></li> <li><a href="/wiki/Turing_machine" title="Turing machine">Turing machine</a></li> <li><a href="/wiki/UML_state_machine" title="UML state machine">UML state machine</a></li></ul> </div> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=23" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <div class="mw-references-wrap mw-references-columns"><ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFWang2019" class="citation book cs1">Wang, Jiacun (2019). <i>Formal Methods in Computer Science</i>. CRC Press. p. 34. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-4987-7532-8" title="Special:BookSources/978-1-4987-7532-8"><bdi>978-1-4987-7532-8</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Formal+Methods+in+Computer+Science&rft.pages=34&rft.pub=CRC+Press&rft.date=2019&rft.isbn=978-1-4987-7532-8&rft.aulast=Wang&rft.aufirst=Jiacun&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://brilliant.org/wiki/finite-state-machines/">"Finite State Machines – Brilliant Math & Science Wiki"</a>. <i>brilliant.org</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2018-04-14</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=brilliant.org&rft.atitle=Finite+State+Machines+%E2%80%93+Brilliant+Math+%26+Science+Wiki&rft_id=https%3A%2F%2Fbrilliant.org%2Fwiki%2Ffinite-state-machines%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></span> </li> <li id="cite_note-Belzer-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-Belzer_3-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBelzerHolzmanKent1975" class="citation book cs1">Belzer, Jack; Holzman, Albert George; Kent, Allen (1975). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=W2YLBIdeLIEC"><i>Encyclopedia of Computer Science and Technology</i></a>. Vol. 25. USA: CRC Press. p. 73. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-8247-2275-3" title="Special:BookSources/978-0-8247-2275-3"><bdi>978-0-8247-2275-3</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Encyclopedia+of+Computer+Science+and+Technology&rft.place=USA&rft.pages=73&rft.pub=CRC+Press&rft.date=1975&rft.isbn=978-0-8247-2275-3&rft.aulast=Belzer&rft.aufirst=Jack&rft.au=Holzman%2C+Albert+George&rft.au=Kent%2C+Allen&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DW2YLBIdeLIEC&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></span> </li> <li id="cite_note-Koshy-4"><span class="mw-cite-backlink">^ <a href="#cite_ref-Koshy_4-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Koshy_4-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKoshy2004" class="citation book cs1">Koshy, Thomas (2004). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=90KApidK5NwC&pg=PA762"><i>Discrete Mathematics With Applications</i></a>. Academic Press. p. 762. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-12-421180-3" title="Special:BookSources/978-0-12-421180-3"><bdi>978-0-12-421180-3</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Discrete+Mathematics+With+Applications&rft.pages=762&rft.pub=Academic+Press&rft.date=2004&rft.isbn=978-0-12-421180-3&rft.aulast=Koshy&rft.aufirst=Thomas&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3D90KApidK5NwC%26pg%3DPA762&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></span> </li> <li id="cite_note-⁇⁇⁇?-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-⁇⁇⁇?_5-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFWright2005" class="citation web cs1">Wright, David R. (2005). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20140327131120/http://www4.ncsu.edu/~drwrigh3/docs/courses/csc216/fsm-notes.pdf">"Finite State Machines"</a> <span class="cs1-format">(PDF)</span>. <i>CSC215 Class Notes</i>. David R. Wright website, N. Carolina State Univ. Archived from <a rel="nofollow" class="external text" href="http://www4.ncsu.edu/~drwrigh3/docs/courses/csc216/fsm-notes.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2014-03-27<span class="reference-accessdate">. Retrieved <span class="nowrap">2012-07-14</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=CSC215+Class+Notes&rft.atitle=Finite+State+Machines&rft.date=2005&rft.aulast=Wright&rft.aufirst=David+R.&rft_id=http%3A%2F%2Fwww4.ncsu.edu%2F~drwrigh3%2Fdocs%2Fcourses%2Fcsc216%2Ffsm-notes.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></span> </li> <li id="cite_note-Keller2001-6"><span class="mw-cite-backlink">^ <a href="#cite_ref-Keller2001_6-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Keller2001_6-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKeller2001" class="citation book cs1">Keller, Robert M. (2001). <a rel="nofollow" class="external text" href="http://www.cs.hmc.edu/~keller/cs60book/12%20Finite-State%20Machines.pdf">"Classifiers, Acceptors, Transducers, and Sequencers"</a> <span class="cs1-format">(PDF)</span>. <a rel="nofollow" class="external text" href="http://www.cs.hmc.edu/~keller/cs60book/%20%20%20All.pdf"><i>Computer Science: Abstraction to Implementation</i></a> <span class="cs1-format">(PDF)</span>. Harvey Mudd College. p. 480.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Classifiers%2C+Acceptors%2C+Transducers%2C+and+Sequencers&rft.btitle=Computer+Science%3A+Abstraction+to+Implementation&rft.pages=480&rft.pub=Harvey+Mudd+College&rft.date=2001&rft.aulast=Keller&rft.aufirst=Robert+M.&rft_id=http%3A%2F%2Fwww.cs.hmc.edu%2F~keller%2Fcs60book%2F12%2520Finite-State%2520Machines.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></span> </li> <li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFJohn_E._Hopcroft_and_Jeffrey_D._Ullman1979" class="citation book cs1">John E. Hopcroft and Jeffrey D. Ullman (1979). <a rel="nofollow" class="external text" href="https://archive.org/details/introductiontoau00hopc"><i>Introduction to Automata Theory, Languages, and Computation</i></a>. Reading/MA: Addison-Wesley. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-201-02988-8" title="Special:BookSources/978-0-201-02988-8"><bdi>978-0-201-02988-8</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Introduction+to+Automata+Theory%2C+Languages%2C+and+Computation&rft.place=Reading%2FMA&rft.pub=Addison-Wesley&rft.date=1979&rft.isbn=978-0-201-02988-8&rft.au=John+E.+Hopcroft+and+Jeffrey+D.+Ullman&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Fintroductiontoau00hopc&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></span> </li> <li id="cite_note-PoulyKohlas2012-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-PoulyKohlas2012_8-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPoulyKohlas2011" class="citation book cs1">Pouly, Marc; Kohlas, Jürg (2011). <i>Generic Inference: A Unifying Theory for Automated Reasoning</i>. John Wiley & Sons. Chapter 6. Valuation Algebras for Path Problems, p. 223 in particular. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-118-01086-0" title="Special:BookSources/978-1-118-01086-0"><bdi>978-1-118-01086-0</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Generic+Inference%3A+A+Unifying+Theory+for+Automated+Reasoning&rft.pages=Chapter+6.+Valuation+Algebras+for+Path+Problems%2C+p.+223+in+particular&rft.pub=John+Wiley+%26+Sons&rft.date=2011&rft.isbn=978-1-118-01086-0&rft.aulast=Pouly&rft.aufirst=Marc&rft.au=Kohlas%2C+J%C3%BCrg&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFJacek_Jonczy2008" class="citation web cs1">Jacek Jonczy (Jun 2008). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20140821054702/http://www.iam.unibe.ch/~run/talks/2008-06-05-Bern-Jonczy.pdf">"Algebraic path problems"</a> <span class="cs1-format">(PDF)</span>. Archived from <a rel="nofollow" class="external text" href="http://www.iam.unibe.ch/~run/talks/2008-06-05-Bern-Jonczy.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2014-08-21<span class="reference-accessdate">. Retrieved <span class="nowrap">2014-08-20</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Algebraic+path+problems&rft.date=2008-06&rft.au=Jacek+Jonczy&rft_id=http%3A%2F%2Fwww.iam.unibe.ch%2F~run%2Ftalks%2F2008-06-05-Bern-Jonczy.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span>, p. 34</span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFelkin2007" class="citation book cs1">Felkin, M. (2007). Guillet, Fabrice; Hamilton, Howard J. (eds.). <i>Quality Measures in Data Mining - Studies in Computational Intelligence</i>. Vol. 43. Springer, Berlin, Heidelberg. pp. 277–278. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-44918-8_12">10.1007/978-3-540-44918-8_12</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-3-540-44911-9" title="Special:BookSources/978-3-540-44911-9"><bdi>978-3-540-44911-9</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Quality+Measures+in+Data+Mining+-+Studies+in+Computational+Intelligence&rft.pages=277-278&rft.pub=Springer%2C+Berlin%2C+Heidelberg&rft.date=2007&rft_id=info%3Adoi%2F10.1007%2F978-3-540-44918-8_12&rft.isbn=978-3-540-44911-9&rft.aulast=Felkin&rft.aufirst=M.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></span> </li> <li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text">Brutscheck, M., Berger, S., Franke, M., Schwarzbacher, A., Becker, S.: Structural Division Procedure for Efficient IC Analysis. IET Irish Signals and Systems Conference, (ISSC 2008), pp.18–23. Galway, Ireland, 18–19 June 2008. <a rel="nofollow" class="external autonumber" href="http://arrow.dit.ie/engschececon/2/">[1]</a></span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.csl.sri.com/users/tiwari/papers/stateflow.pdf">"Tiwari, A. (2002). Formal Semantics and Analysis Methods for Simulink Stateflow Models"</a> <span class="cs1-format">(PDF)</span>. <i>sri.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2018-04-14</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=sri.com&rft.atitle=Tiwari%2C+A.+%282002%29.+Formal+Semantics+and+Analysis+Methods+for+Simulink+Stateflow+Models.&rft_id=http%3A%2F%2Fwww.csl.sri.com%2Fusers%2Ftiwari%2Fpapers%2Fstateflow.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></span> </li> <li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHamon2005" class="citation conference cs1">Hamon, G. (2005). <i>A Denotational Semantics for Stateflow</i>. International Conference on Embedded Software. Jersey City, NJ: ACM. pp. 164–172. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.89.8817">10.1.1.89.8817</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.btitle=A+Denotational+Semantics+for+Stateflow&rft.place=Jersey+City%2C+NJ&rft.pages=164-172&rft.pub=ACM&rft.date=2005&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.89.8817%23id-name%3DCiteSeerX&rft.aulast=Hamon&rft.aufirst=G.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></span> </li> <li id="cite_note-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-14">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20110715110405/http://www.fceia.unr.edu.ar/asist/harel01.pdf">"Harel, D. (1987). A Visual Formalism for Complex Systems. Science of Computer Programming, 231–274"</a> <span class="cs1-format">(PDF)</span>. Archived from <a rel="nofollow" class="external text" href="http://www.fceia.unr.edu.ar/asist/harel01.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2011-07-15<span class="reference-accessdate">. Retrieved <span class="nowrap">2011-06-07</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Harel%2C+D.+%281987%29.+A+Visual+Formalism+for+Complex+Systems.+Science+of+Computer+Programming%2C+231%E2%80%93274.&rft_id=http%3A%2F%2Fwww.fceia.unr.edu.ar%2Fasist%2Fharel01.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></span> </li> <li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20110715110405/http://drona.csa.iisc.ernet.in/~kanade/publications/symbolic_analysis_for_improving_simulation_coverage_of_simulink_stateflow_models.pdf">"Alur, R., Kanade, A., Ramesh, S., & Shashidhar, K. C. (2008). Symbolic analysis for improving simulation coverage of Simulink/Stateflow models. International Conference on Embedded Software (pp. 89–98). Atlanta, GA: ACM"</a> <span class="cs1-format">(PDF)</span>. Archived from <a rel="nofollow" class="external text" href="http://drona.csa.iisc.ernet.in/~kanade/publications/symbolic_analysis_for_improving_simulation_coverage_of_simulink_stateflow_models.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2011-07-15.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Alur%2C+R.%2C+Kanade%2C+A.%2C+Ramesh%2C+S.%2C+%26+Shashidhar%2C+K.+C.+%282008%29.+Symbolic+analysis+for+improving+simulation+coverage+of+Simulink%2FStateflow+models.+International+Conference+on+Embedded+Software+%28pp.+89%E2%80%9398%29.+Atlanta%2C+GA%3A+ACM.&rft_id=http%3A%2F%2Fdrona.csa.iisc.ernet.in%2F~kanade%2Fpublications%2Fsymbolic_analysis_for_improving_simulation_coverage_of_simulink_stateflow_models.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></span> </li> <li id="cite_note-16"><span class="mw-cite-backlink"><b><a href="#cite_ref-16">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBlack2008" class="citation journal cs1">Black, Paul E (12 May 2008). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20181013023517/https://xlinux.nist.gov/dads/HTML/finiteStateMachine.html">"Finite State Machine"</a>. <i>Dictionary of Algorithms and Data Structures</i>. U.S. <a href="/wiki/National_Institute_of_Standards_and_Technology" title="National Institute of Standards and Technology">National Institute of Standards and Technology</a>. Archived from <a rel="nofollow" class="external text" href="https://xlinux.nist.gov/dads/HTML/finiteStateMachine.html">the original</a> on 13 October 2018<span class="reference-accessdate">. Retrieved <span class="nowrap">2 November</span> 2016</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Dictionary+of+Algorithms+and+Data+Structures&rft.atitle=Finite+State+Machine&rft.date=2008-05-12&rft.aulast=Black&rft.aufirst=Paul+E&rft_id=https%3A%2F%2Fxlinux.nist.gov%2Fdads%2FHTML%2FfiniteStateMachine.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></span> </li> <li id="cite_note-AndersonHead2006-17"><span class="mw-cite-backlink"><b><a href="#cite_ref-AndersonHead2006_17-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAndersonHead2006" class="citation book cs1">Anderson, James Andrew; Head, Thomas J. (2006). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=ikS8BLdLDxIC&pg=PA105"><i>Automata theory with modern applications</i></a>. Cambridge University Press. pp. 105–108. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-521-84887-9" title="Special:BookSources/978-0-521-84887-9"><bdi>978-0-521-84887-9</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Automata+theory+with+modern+applications&rft.pages=105-108&rft.pub=Cambridge+University+Press&rft.date=2006&rft.isbn=978-0-521-84887-9&rft.aulast=Anderson&rft.aufirst=James+Andrew&rft.au=Head%2C+Thomas+J.&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DikS8BLdLDxIC%26pg%3DPA105&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></span> </li> <li id="cite_note-18"><span class="mw-cite-backlink"><b><a href="#cite_ref-18">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHopcroft1971" class="citation report cs1 cs1-prop-long-vol">Hopcroft, John E. (1971). <a rel="nofollow" class="external text" href="ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/71/190/CS-TR-71-190.pdf">An <i>n</i> log <i>n</i> algorithm for minimizing states in a finite automaton</a> <span class="cs1-format">(PDF)</span> (Technical Report). Vol. CS-TR-71-190. Stanford Univ.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=report&rft.btitle=An+n+log+n+algorithm+for+minimizing+states+in+a+finite+automaton&rft.pub=Stanford+Univ.&rft.date=1971&rft.aulast=Hopcroft&rft.aufirst=John+E.&rft_id=ftp%3A%2F%2Freports.stanford.edu%2Fpub%2Fcstr%2Freports%2Fcs%2Ftr%2F71%2F190%2FCS-TR-71-190.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span><sup class="noprint Inline-Template"><span style="white-space: nowrap;">[<i><a href="/wiki/Wikipedia:Link_rot" title="Wikipedia:Link rot"><span title=" Dead link tagged October 2017">permanent dead link</span></a></i><span style="visibility:hidden; color:transparent; padding-left:2px">‍</span>]</span></sup></span> </li> <li id="cite_note-19"><span class="mw-cite-backlink"><b><a href="#cite_ref-19">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAlmeidaMoreiraReis2007" class="citation report cs1 cs1-prop-long-vol">Almeida, Marco; Moreira, Nelma; Reis, Rogerio (2007). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20090117201637/http://www.dcc.fc.up.pt/dcc/Pubs/TReports/TR07/dcc-2007-03.pdf">On the performance of automata minimization algorithms</a> <span class="cs1-format">(PDF)</span> (Technical Report). Vol. DCC-2007-03. Porto Univ. Archived from <a rel="nofollow" class="external text" href="http://www.dcc.fc.up.pt/dcc/Pubs/TReports/TR07/dcc-2007-03.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 17 January 2009<span class="reference-accessdate">. Retrieved <span class="nowrap">25 June</span> 2008</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=report&rft.btitle=On+the+performance+of+automata+minimization+algorithms&rft.pub=Porto+Univ.&rft.date=2007&rft.aulast=Almeida&rft.aufirst=Marco&rft.au=Moreira%2C+Nelma&rft.au=Reis%2C+Rogerio&rft_id=http%3A%2F%2Fwww.dcc.fc.up.pt%2Fdcc%2FPubs%2FTReports%2FTR07%2Fdcc-2007-03.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></span> </li> <li id="cite_note-20"><span class="mw-cite-backlink"><b><a href="#cite_ref-20">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFEdward_F._Moore1956" class="citation journal cs1">Edward F. Moore (1956). C.E. Shannon and J. McCarthy (ed.). "Gedanken-Experiments on Sequential Machines". <i>Annals of Mathematics Studies</i>. <b>34</b>. Princeton University Press: 129–153.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Annals+of+Mathematics+Studies&rft.atitle=Gedanken-Experiments+on+Sequential+Machines&rft.volume=34&rft.pages=129-153&rft.date=1956&rft.au=Edward+F.+Moore&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span> Here: Theorem 4, p.142.</span> </li> <li id="cite_note-21"><span class="mw-cite-backlink"><b><a href="#cite_ref-21">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRevuz1992" class="citation journal cs1">Revuz, D. (1992). "Minimization of Acyclic automata in Linear Time". <i>Theoretical Computer Science</i>. <b>92</b>: 181–189. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0304-3975%2892%2990142-3">10.1016/0304-3975(92)90142-3</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Theoretical+Computer+Science&rft.atitle=Minimization+of+Acyclic+automata+in+Linear+Time&rft.volume=92&rft.pages=181-189&rft.date=1992&rft_id=info%3Adoi%2F10.1016%2F0304-3975%2892%2990142-3&rft.aulast=Revuz&rft.aufirst=D.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></span> </li> <li id="cite_note-22"><span class="mw-cite-backlink"><b><a href="#cite_ref-22">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKaeslin2008" class="citation book cs1">Kaeslin, Hubert (2008). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=gdRStcYgf2oC&q=medvedev+fsm&pg=PA787">"Mealy, Moore, Medvedev-type and combinatorial output bits"</a>. <i>Digital Integrated Circuit Design: From VLSI Architectures to CMOS Fabrication</i>. Cambridge University Press. p. 787. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-521-88267-5" title="Special:BookSources/978-0-521-88267-5"><bdi>978-0-521-88267-5</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Mealy%2C+Moore%2C+Medvedev-type+and+combinatorial+output+bits&rft.btitle=Digital+Integrated+Circuit+Design%3A+From+VLSI+Architectures+to+CMOS+Fabrication&rft.pages=787&rft.pub=Cambridge+University+Press&rft.date=2008&rft.isbn=978-0-521-88267-5&rft.aulast=Kaeslin&rft.aufirst=Hubert&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3DgdRStcYgf2oC%26q%3Dmedvedev%2Bfsm%26pg%3DPA787&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></span> </li> <li id="cite_note-23"><span class="mw-cite-backlink"><b><a href="#cite_ref-23">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://users.etech.haw-hamburg.de/users/Schwarz/En/Lecture/Ds/Notes/DigSys1.pdf">Slides</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170118123034/http://users.etech.haw-hamburg.de/users/Schwarz/En/Lecture/Ds/Notes/DigSys1.pdf">Archived</a> 18 January 2017 at the <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a>, <i>Synchronous Finite State Machines; Design and Behaviour</i>, <a href="/wiki/University_of_Applied_Sciences_Hamburg" class="mw-redirect" title="University of Applied Sciences Hamburg">University of Applied Sciences Hamburg</a>, p.18</span> </li> <li id="cite_note-24"><span class="mw-cite-backlink"><b><a href="#cite_ref-24">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAhoSethiUllman1986" class="citation book cs1"><a href="/wiki/Alfred_V._Aho" class="mw-redirect" title="Alfred V. Aho">Aho, Alfred V.</a>; <a href="/wiki/Ravi_Sethi" title="Ravi Sethi">Sethi, Ravi</a>; <a href="/wiki/Jeffrey_D._Ullman" class="mw-redirect" title="Jeffrey D. Ullman">Ullman, Jeffrey D.</a> (1986). <a href="/wiki/Compilers:_Principles,_Techniques,_and_Tools" title="Compilers: Principles, Techniques, and Tools"><i>Compilers: Principles, Techniques, and Tools</i></a> (1st ed.). <a href="/wiki/Addison-Wesley" title="Addison-Wesley">Addison-Wesley</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-201-10088-4" title="Special:BookSources/978-0-201-10088-4"><bdi>978-0-201-10088-4</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Compilers%3A+Principles%2C+Techniques%2C+and+Tools&rft.edition=1st&rft.pub=Addison-Wesley&rft.date=1986&rft.isbn=978-0-201-10088-4&rft.aulast=Aho&rft.aufirst=Alfred+V.&rft.au=Sethi%2C+Ravi&rft.au=Ullman%2C+Jeffrey+D.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=24" title="Edit section: Further reading"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="General">General</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=25" title="Edit section: General"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSakarovitch2009" class="citation book cs1">Sakarovitch, Jacques (2009). <i>Elements of automata theory</i>. Translated from the French by Reuben Thomas. <a href="/wiki/Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-521-84425-3" title="Special:BookSources/978-0-521-84425-3"><bdi>978-0-521-84425-3</bdi></a>. <a href="/wiki/Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:1188.68177">1188.68177</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Elements+of+automata+theory&rft.pub=Cambridge+University+Press&rft.date=2009&rft_id=https%3A%2F%2Fzbmath.org%2F%3Fformat%3Dcomplete%26q%3Dan%3A1188.68177%23id-name%3DZbl&rft.isbn=978-0-521-84425-3&rft.aulast=Sakarovitch&rft.aufirst=Jacques&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></li> <li>Wagner, F., "Modeling Software with Finite State Machines: A Practical Approach", Auerbach Publications, 2006, <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-8493-8086-3" title="Special:BookSources/0-8493-8086-3">0-8493-8086-3</a>.</li> <li>ITU-T, <a rel="nofollow" class="external text" href="http://www.itu.int/rec/T-REC-Z.100-200711-I/en"><i>Recommendation Z.100 Specification and Description Language (SDL)</i></a></li> <li>Samek, M., <a rel="nofollow" class="external text" href="http://www.state-machine.com/psicc/index.php"><i>Practical Statecharts in C/C++</i></a>, CMP Books, 2002, <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/1-57820-110-1" title="Special:BookSources/1-57820-110-1">1-57820-110-1</a>.</li> <li>Samek, M., <a rel="nofollow" class="external text" href="http://www.state-machine.com/psicc2/index.php"><i>Practical UML Statecharts in C/C++, 2nd Edition</i></a>, Newnes, 2008, <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-7506-8706-1" title="Special:BookSources/0-7506-8706-1">0-7506-8706-1</a>.</li> <li>Gardner, T., <a rel="nofollow" class="external text" href="http://www.troyworks.com/cogs/"><i>Advanced State Management</i></a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20081119071252/http://www.troyworks.com/cogs/">Archived</a> 2008-11-19 at the <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a>, 2007</li> <li>Cassandras, C., Lafortune, S., "Introduction to Discrete Event Systems". Kluwer, 1999, <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-7923-8609-4" title="Special:BookSources/0-7923-8609-4">0-7923-8609-4</a>.</li> <li>Timothy Kam, <i>Synthesis of Finite State Machines: Functional Optimization</i>. Kluwer Academic Publishers, Boston 1997, <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-7923-9842-4" title="Special:BookSources/0-7923-9842-4">0-7923-9842-4</a></li> <li>Tiziano Villa, <i>Synthesis of Finite State Machines: Logic Optimization</i>. Kluwer Academic Publishers, Boston 1997, <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-7923-9892-0" title="Special:BookSources/0-7923-9892-0">0-7923-9892-0</a></li> <li>Carroll, J., Long, D., <i><a rel="nofollow" class="external text" href="https://philpapers.org/archive/CARTOF.pdf">Theory of Finite Automata with an Introduction to Formal Languages</a></i>. Prentice Hall, Englewood Cliffs, 1989.</li> <li>Kohavi, Z., <i>Switching and Finite Automata Theory</i>. McGraw-Hill, 1978.</li> <li>Gill, A., <i>Introduction to the Theory of Finite-state Machines</i>. McGraw-Hill, 1962.</li> <li>Ginsburg, S., <i>An Introduction to Mathematical Machine Theory</i>. Addison-Wesley, 1962.</li></ul> <div class="mw-heading mw-heading3"><h3 id="Finite-state_machines_(automata_theory)_in_theoretical_computer_science"><span id="Finite-state_machines_.28automata_theory.29_in_theoretical_computer_science"></span>Finite-state machines (automata theory) in theoretical computer science</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=26" title="Edit section: Finite-state machines (automata theory) in theoretical computer science"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFArbib1969" class="citation book cs1">Arbib, Michael A. (1969). <i>Theories of Abstract Automata</i> (1st ed.). Englewood Cliffs, N.J.: Prentice-Hall, Inc. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-13-913368-8" title="Special:BookSources/978-0-13-913368-8"><bdi>978-0-13-913368-8</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Theories+of+Abstract+Automata&rft.place=Englewood+Cliffs%2C+N.J.&rft.edition=1st&rft.pub=Prentice-Hall%2C+Inc.&rft.date=1969&rft.isbn=978-0-13-913368-8&rft.aulast=Arbib&rft.aufirst=Michael+A.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBobrowArbib1974" class="citation book cs1">Bobrow, Leonard S.; Arbib, Michael A. (1974). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/discretemathemat0000bobr"><i>Discrete Mathematics: Applied Algebra for Computer and Information Science</i></a></span> (1st ed.). Philadelphia: W. B. Saunders Company, Inc. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-7216-1768-8" title="Special:BookSources/978-0-7216-1768-8"><bdi>978-0-7216-1768-8</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Discrete+Mathematics%3A+Applied+Algebra+for+Computer+and+Information+Science&rft.place=Philadelphia&rft.edition=1st&rft.pub=W.+B.+Saunders+Company%2C+Inc.&rft.date=1974&rft.isbn=978-0-7216-1768-8&rft.aulast=Bobrow&rft.aufirst=Leonard+S.&rft.au=Arbib%2C+Michael+A.&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Fdiscretemathemat0000bobr&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBooth1967" class="citation book cs1">Booth, Taylor L. (1967). <i>Sequential Machines and Automata Theory</i> (1st ed.). New York: John Wiley and Sons, Inc. Library of Congress Card Catalog Number 67-25924.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Sequential+Machines+and+Automata+Theory&rft.place=New+York&rft.edition=1st&rft.pub=John+Wiley+and+Sons%2C+Inc.&rft.date=1967&rft.aulast=Booth&rft.aufirst=Taylor+L.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBoolosJeffrey1999" class="citation book cs1">Boolos, George; Jeffrey, Richard (1999) [1989]. <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/computabilitylog0000bool_r8y9"><i>Computability and Logic</i></a></span> (3rd ed.). Cambridge, England: Cambridge University Press. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-521-20402-6" title="Special:BookSources/978-0-521-20402-6"><bdi>978-0-521-20402-6</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Computability+and+Logic&rft.place=Cambridge%2C+England&rft.edition=3rd&rft.pub=Cambridge+University+Press&rft.date=1999&rft.isbn=978-0-521-20402-6&rft.aulast=Boolos&rft.aufirst=George&rft.au=Jeffrey%2C+Richard&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Fcomputabilitylog0000bool_r8y9&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBrookshear1989" class="citation book cs1">Brookshear, J. Glenn (1989). <i>Theory of Computation: Formal Languages, Automata, and Complexity</i>. Redwood City, California: Benjamin/Cummings Publish Company, Inc. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-8053-0143-4" title="Special:BookSources/978-0-8053-0143-4"><bdi>978-0-8053-0143-4</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Theory+of+Computation%3A+Formal+Languages%2C+Automata%2C+and+Complexity&rft.place=Redwood+City%2C+California&rft.pub=Benjamin%2FCummings+Publish+Company%2C+Inc.&rft.date=1989&rft.isbn=978-0-8053-0143-4&rft.aulast=Brookshear&rft.aufirst=J.+Glenn&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDavisSigalWeyuker1994" class="citation book cs1">Davis, Martin; Sigal, Ron; Weyuker, Elaine J. (1994). <i>Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science</i> (2nd ed.). San Diego: Academic Press, Harcourt, Brace & Company. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-12-206382-4" title="Special:BookSources/978-0-12-206382-4"><bdi>978-0-12-206382-4</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Computability%2C+Complexity%2C+and+Languages+and+Logic%3A+Fundamentals+of+Theoretical+Computer+Science&rft.place=San+Diego&rft.edition=2nd&rft.pub=Academic+Press%2C+Harcourt%2C+Brace+%26+Company&rft.date=1994&rft.isbn=978-0-12-206382-4&rft.aulast=Davis&rft.aufirst=Martin&rft.au=Sigal%2C+Ron&rft.au=Weyuker%2C+Elaine+J.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHopcroftUllman1979" class="citation book cs1">Hopcroft, John; Ullman, Jeffrey (1979). <a href="/wiki/Introduction_to_Automata_Theory,_Languages,_and_Computation" title="Introduction to Automata Theory, Languages, and Computation"><i>Introduction to Automata Theory, Languages, and Computation</i></a> (1st ed.). Reading Mass: Addison-Wesley. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-201-02988-8" title="Special:BookSources/978-0-201-02988-8"><bdi>978-0-201-02988-8</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Introduction+to+Automata+Theory%2C+Languages%2C+and+Computation&rft.place=Reading+Mass&rft.edition=1st&rft.pub=Addison-Wesley&rft.date=1979&rft.isbn=978-0-201-02988-8&rft.aulast=Hopcroft&rft.aufirst=John&rft.au=Ullman%2C+Jeffrey&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHopcroftMotwaniUllman2001" class="citation book cs1">Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). <i>Introduction to Automata Theory, Languages, and Computation</i> (2nd ed.). Reading Mass: Addison-Wesley. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-201-44124-6" title="Special:BookSources/978-0-201-44124-6"><bdi>978-0-201-44124-6</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Introduction+to+Automata+Theory%2C+Languages%2C+and+Computation&rft.place=Reading+Mass&rft.edition=2nd&rft.pub=Addison-Wesley&rft.date=2001&rft.isbn=978-0-201-44124-6&rft.aulast=Hopcroft&rft.aufirst=John+E.&rft.au=Motwani%2C+Rajeev&rft.au=Ullman%2C+Jeffrey+D.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHopkinMoss1976" class="citation book cs1">Hopkin, David; Moss, Barbara (1976). <i>Automata</i>. New York: Elsevier North-Holland. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-444-00249-5" title="Special:BookSources/978-0-444-00249-5"><bdi>978-0-444-00249-5</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Automata&rft.place=New+York&rft.pub=Elsevier+North-Holland&rft.date=1976&rft.isbn=978-0-444-00249-5&rft.aulast=Hopkin&rft.aufirst=David&rft.au=Moss%2C+Barbara&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKozen1997" class="citation book cs1">Kozen, Dexter C. (1997). <i>Automata and Computability</i> (1st ed.). New York: Springer-Verlag. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-387-94907-9" title="Special:BookSources/978-0-387-94907-9"><bdi>978-0-387-94907-9</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Automata+and+Computability&rft.place=New+York&rft.edition=1st&rft.pub=Springer-Verlag&rft.date=1997&rft.isbn=978-0-387-94907-9&rft.aulast=Kozen&rft.aufirst=Dexter+C.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFLewisPapadimitriou1998" class="citation book cs1"><a href="/wiki/Harry_R._Lewis" title="Harry R. Lewis">Lewis, Harry R.</a>; <a href="/wiki/Christos_H._Papadimitriou" class="mw-redirect" title="Christos H. Papadimitriou">Papadimitriou, Christos H.</a> (1998). <i>Elements of the Theory of Computation</i> (2nd ed.). Upper Saddle River, New Jersey: Prentice-Hall. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-13-262478-7" title="Special:BookSources/978-0-13-262478-7"><bdi>978-0-13-262478-7</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Elements+of+the+Theory+of+Computation&rft.place=Upper+Saddle+River%2C+New+Jersey&rft.edition=2nd&rft.pub=Prentice-Hall&rft.date=1998&rft.isbn=978-0-13-262478-7&rft.aulast=Lewis&rft.aufirst=Harry+R.&rft.au=Papadimitriou%2C+Christos+H.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFLinz2006" class="citation book cs1">Linz, Peter (2006). <i>Formal Languages and Automata</i> (4th ed.). Sudbury, MA: Jones and Bartlett. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-7637-3798-6" title="Special:BookSources/978-0-7637-3798-6"><bdi>978-0-7637-3798-6</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Formal+Languages+and+Automata&rft.place=Sudbury%2C+MA&rft.edition=4th&rft.pub=Jones+and+Bartlett&rft.date=2006&rft.isbn=978-0-7637-3798-6&rft.aulast=Linz&rft.aufirst=Peter&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMinsky1967" class="citation book cs1">Minsky, Marvin (1967). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/computationfinit0000mins"><i>Computation: Finite and Infinite Machines</i></a></span> (1st ed.). New Jersey: Prentice-Hall.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Computation%3A+Finite+and+Infinite+Machines&rft.place=New+Jersey&rft.edition=1st&rft.pub=Prentice-Hall&rft.date=1967&rft.aulast=Minsky&rft.aufirst=Marvin&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Fcomputationfinit0000mins&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPapadimitriou1993" class="citation book cs1"><a href="/wiki/Christos_Papadimitriou" title="Christos Papadimitriou">Papadimitriou, Christos</a> (1993). <i>Computational Complexity</i> (1st ed.). Addison Wesley. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-201-53082-7" title="Special:BookSources/978-0-201-53082-7"><bdi>978-0-201-53082-7</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Computational+Complexity&rft.edition=1st&rft.pub=Addison+Wesley&rft.date=1993&rft.isbn=978-0-201-53082-7&rft.aulast=Papadimitriou&rft.aufirst=Christos&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPippenger1997" class="citation book cs1">Pippenger, Nicholas (1997). <i>Theories of Computability</i> (1st ed.). Cambridge, England: Cambridge University Press. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-521-55380-3" title="Special:BookSources/978-0-521-55380-3"><bdi>978-0-521-55380-3</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Theories+of+Computability&rft.place=Cambridge%2C+England&rft.edition=1st&rft.pub=Cambridge+University+Press&rft.date=1997&rft.isbn=978-0-521-55380-3&rft.aulast=Pippenger&rft.aufirst=Nicholas&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRodgerFinley2006" class="citation book cs1">Rodger, Susan; Finley, Thomas (2006). <i>JFLAP: An Interactive Formal Languages and Automata Package</i> (1st ed.). Sudbury, MA: Jones and Bartlett. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-7637-3834-1" title="Special:BookSources/978-0-7637-3834-1"><bdi>978-0-7637-3834-1</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=JFLAP%3A+An+Interactive+Formal+Languages+and+Automata+Package&rft.place=Sudbury%2C+MA&rft.edition=1st&rft.pub=Jones+and+Bartlett&rft.date=2006&rft.isbn=978-0-7637-3834-1&rft.aulast=Rodger&rft.aufirst=Susan&rft.au=Finley%2C+Thomas&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSipser2006" class="citation book cs1">Sipser, Michael (2006). <i>Introduction to the Theory of Computation</i> (2nd ed.). Boston Mass: Thomson Course Technology. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-534-95097-2" title="Special:BookSources/978-0-534-95097-2"><bdi>978-0-534-95097-2</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Introduction+to+the+Theory+of+Computation&rft.place=Boston+Mass&rft.edition=2nd&rft.pub=Thomson+Course+Technology&rft.date=2006&rft.isbn=978-0-534-95097-2&rft.aulast=Sipser&rft.aufirst=Michael&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFWood1987" class="citation book cs1"><a href="/wiki/Derick_Wood" title="Derick Wood">Wood, Derick</a> (1987). <i>Theory of Computation</i> (1st ed.). New York: Harper & Row, Publishers, Inc. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-06-047208-5" title="Special:BookSources/978-0-06-047208-5"><bdi>978-0-06-047208-5</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Theory+of+Computation&rft.place=New+York&rft.edition=1st&rft.pub=Harper+%26+Row%2C+Publishers%2C+Inc.&rft.date=1987&rft.isbn=978-0-06-047208-5&rft.aulast=Wood&rft.aufirst=Derick&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></li></ul> <div class="mw-heading mw-heading3"><h3 id="Abstract_state_machines_in_theoretical_computer_science">Abstract state machines in theoretical computer science</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=27" title="Edit section: Abstract state machines in theoretical computer science"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGurevich2000" class="citation journal cs1">Gurevich, Yuri (July 2000). <a rel="nofollow" class="external text" href="http://research.microsoft.com/~gurevich/Opera/141.pdf">"Sequential Abstract State Machines Capture Sequential Algorithms"</a> <span class="cs1-format">(PDF)</span>. <i>ACM Transactions on Computational Logic</i>. <b>1</b> (1): 77–111. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.146.3017">10.1.1.146.3017</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F343369.343384">10.1145/343369.343384</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2031696">2031696</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=ACM+Transactions+on+Computational+Logic&rft.atitle=Sequential+Abstract+State+Machines+Capture+Sequential+Algorithms&rft.volume=1&rft.issue=1&rft.pages=77-111&rft.date=2000-07&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.146.3017%23id-name%3DCiteSeerX&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A2031696%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F343369.343384&rft.aulast=Gurevich&rft.aufirst=Yuri&rft_id=http%3A%2F%2Fresearch.microsoft.com%2F~gurevich%2FOpera%2F141.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></li></ul> <div class="mw-heading mw-heading3"><h3 id="Machine_learning_using_finite-state_algorithms">Machine learning using finite-state algorithms</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=28" title="Edit section: Machine learning using finite-state algorithms"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMitchell1997" class="citation book cs1">Mitchell, Tom M. (1997). <i>Machine Learning</i> (1st ed.). New York: WCB/McGraw-Hill Corporation. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-07-042807-2" title="Special:BookSources/978-0-07-042807-2"><bdi>978-0-07-042807-2</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Machine+Learning&rft.place=New+York&rft.edition=1st&rft.pub=WCB%2FMcGraw-Hill+Corporation&rft.date=1997&rft.isbn=978-0-07-042807-2&rft.aulast=Mitchell&rft.aufirst=Tom+M.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></li></ul> <div class="mw-heading mw-heading3"><h3 id="Hardware_engineering:_state_minimization_and_synthesis_of_sequential_circuits">Hardware engineering: state minimization and synthesis of sequential circuits</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=29" title="Edit section: Hardware engineering: state minimization and synthesis of sequential circuits"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBooth1967" class="citation book cs1">Booth, Taylor L. (1967). <i>Sequential Machines and Automata Theory</i> (1st ed.). New York: John Wiley and Sons, Inc. Library of Congress Card Catalog Number 67-25924.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Sequential+Machines+and+Automata+Theory&rft.place=New+York&rft.edition=1st&rft.pub=John+Wiley+and+Sons%2C+Inc.&rft.date=1967&rft.aulast=Booth&rft.aufirst=Taylor+L.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBooth1971" class="citation book cs1">Booth, Taylor L. (1971). <a rel="nofollow" class="external text" href="https://archive.org/details/digitalnetworksc00boot"><i>Digital Networks and Computer Systems</i></a> (1st ed.). New York: John Wiley and Sons, Inc. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-471-08840-0" title="Special:BookSources/978-0-471-08840-0"><bdi>978-0-471-08840-0</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Digital+Networks+and+Computer+Systems&rft.place=New+York&rft.edition=1st&rft.pub=John+Wiley+and+Sons%2C+Inc.&rft.date=1971&rft.isbn=978-0-471-08840-0&rft.aulast=Booth&rft.aufirst=Taylor+L.&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Fdigitalnetworksc00boot&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMcCluskey1965" class="citation book cs1">McCluskey, E. J. (1965). <i>Introduction to the Theory of Switching Circuits</i> (1st ed.). New York: McGraw-Hill Book Company, Inc. Library of Congress Card Catalog Number 65-17394.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Introduction+to+the+Theory+of+Switching+Circuits&rft.place=New+York&rft.edition=1st&rft.pub=McGraw-Hill+Book+Company%2C+Inc.&rft.date=1965&rft.aulast=McCluskey&rft.aufirst=E.+J.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHillPeterson1965" class="citation book cs1">Hill, Fredrick J.; Peterson, Gerald R. (1965). <i>Introduction to the Theory of Switching Circuits</i> (1st ed.). New York: McGraw-Hill Book Company. Library of Congress Card Catalog Number 65-17394.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Introduction+to+the+Theory+of+Switching+Circuits&rft.place=New+York&rft.edition=1st&rft.pub=McGraw-Hill+Book+Company&rft.date=1965&rft.aulast=Hill&rft.aufirst=Fredrick+J.&rft.au=Peterson%2C+Gerald+R.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></li></ul> <div class="mw-heading mw-heading3"><h3 id="Finite_Markov_chain_processes">Finite Markov chain processes</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=30" title="Edit section: Finite Markov chain processes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <dl><dd><dl><dd>"We may think of a <a href="/wiki/Markov_chain" title="Markov chain">Markov chain</a> as a process that moves successively through a set of states <i>s<sub>1</sub></i>, <i>s<sub>2</sub></i>, …, <i>s<sub>r</sub></i>. … if it is in state <i>s<sub>i</sub></i> it moves on to the next stop to state <i>s<sub>j</sub></i> with probability <i>p<sub>ij</sub></i>. These probabilities can be exhibited in the form of a transition matrix" (Kemeny (1959), p. 384)</dd></dl></dd></dl> <p>Finite Markov-chain processes are also known as <a href="/wiki/Subshifts_of_finite_type" class="mw-redirect" title="Subshifts of finite type">subshifts of finite type</a>. </p> <ul><li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBooth1967" class="citation book cs1">Booth, Taylor L. (1967). <i>Sequential Machines and Automata Theory</i> (1st ed.). New York: John Wiley and Sons, Inc. Library of Congress Card Catalog Number 67-25924.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Sequential+Machines+and+Automata+Theory&rft.place=New+York&rft.edition=1st&rft.pub=John+Wiley+and+Sons%2C+Inc.&rft.date=1967&rft.aulast=Booth&rft.aufirst=Taylor+L.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKemenyMirkilSnellThompson1959" class="citation book cs1">Kemeny, John G.; Mirkil, Hazleton; Snell, J. Laurie; Thompson, Gerald L. (1959). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/finitemathematic0000keme_h5g0"><i>Finite Mathematical Structures</i></a></span> (1st ed.). Englewood Cliffs, N.J.: Prentice-Hall, Inc. Library of Congress Card Catalog Number 59-12841.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Finite+Mathematical+Structures&rft.place=Englewood+Cliffs%2C+N.J.&rft.edition=1st&rft.pub=Prentice-Hall%2C+Inc.&rft.date=1959&rft.aulast=Kemeny&rft.aufirst=John+G.&rft.au=Mirkil%2C+Hazleton&rft.au=Snell%2C+J.+Laurie&rft.au=Thompson%2C+Gerald+L.&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Ffinitemathematic0000keme_h5g0&rfr_id=info%3Asid%2Fen.wikipedia.org%3AFinite-state+machine" class="Z3988"></span> Chapter 6 "Finite Markov Chains".</li></ul> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Finite-state_machine&action=edit&section=31" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a rel="nofollow" class="external text" href="https://archive.today/20121202054532/http://blog.manuvra.com/modeling-a-simple-ai-behavior-using-a-finite-state-machine/"><i>Modeling a Simple AI behavior using a Finite State Machine</i></a> Example of usage in Video Games</li> <li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20171211180457/http://foldoc.org/finite+state+machine">Free On-Line Dictionary of Computing</a> description of Finite-State Machines</li> <li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20181013023517/https://xlinux.nist.gov/dads/HTML/finiteStateMachine.html">NIST Dictionary of Algorithms and Data Structures</a> description of Finite-State Machines</li> <li><a rel="nofollow" class="external text" href="https://blogs.itemis.com/en/a-brief-overview-of-state-machine-types">A brief overview of state machine types</a>, comparing theoretical aspects of Mealy, Moore, Harel & UML state machines.</li></ul> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1126788409">.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Automata_theory:_formal_languages_and_formal_grammars" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Formal_languages_and_grammars" title="Template:Formal languages and grammars"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Formal_languages_and_grammars" title="Template talk:Formal languages and grammars"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Formal_languages_and_grammars" title="Special:EditPage/Template:Formal languages and grammars"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Automata_theory:_formal_languages_and_formal_grammars" style="font-size:114%;margin:0 4em"><a href="/wiki/Automata_theory" title="Automata theory">Automata theory</a>: <a href="/wiki/Formal_language" title="Formal language">formal languages</a> and <a href="/wiki/Formal_grammar" title="Formal grammar">formal grammars</a></div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd plainlist" style="width:100%;padding:0;background:transparent;color:inherit;"><div style="padding:0px"><table class="navbox-columns-table" style="border-spacing: 0px; text-align:left;width:100%;"><tbody><tr><td class="navbox-abovebelow" style="font-weight:bold;"><a href="/wiki/Chomsky_hierarchy" title="Chomsky hierarchy">Chomsky hierarchy</a></td><td class="navbox-abovebelow" style="border-left:2px solid #fdfdfd;font-weight:bold;"><a href="/wiki/Formal_grammar" title="Formal grammar">Grammars</a></td><td class="navbox-abovebelow" style="border-left:2px solid #fdfdfd;font-weight:bold;"><a href="/wiki/Formal_language" title="Formal language">Languages</a></td><td class="navbox-abovebelow" style="border-left:2px solid #fdfdfd;font-weight:bold;"><a href="/wiki/Abstract_machine" title="Abstract machine">Abstract machines</a></td></tr><tr style="vertical-align:top"><td class="navbox-list" style="padding:0px;text-align: center;width:10em;"><div> <ul><li>Type-0</li> <li>—</li> <li>Type-1</li> <li>—</li> <li>—</li> <li>—</li> <li>—</li> <li>—</li> <li>Type-2</li> <li>—</li> <li>—</li> <li>Type-3</li> <li>—</li> <li>—</li></ul> </div></td><td class="navbox-list" style="border-left:2px solid #fdfdfd;padding:0px;width:10em;"><div> <ul><li><a href="/wiki/Unrestricted_grammar" title="Unrestricted grammar">Unrestricted</a></li> <li>(no common name)</li> <li><a href="/wiki/Context-sensitive_grammar" title="Context-sensitive grammar">Context-sensitive</a></li> <li><span style="white-space:nowrap;">Positive <a href="/wiki/Range_concatenation_grammars" class="mw-redirect" title="Range concatenation grammars">range concatenation</a></span></li> <li><a href="/wiki/Indexed_grammar" title="Indexed grammar">Indexed</a></li> <li>—</li> <li><a href="/wiki/Linear_context-free_rewriting_system" class="mw-redirect" title="Linear context-free rewriting system">Linear context-free rewriting systems</a></li> <li><a href="/wiki/Tree-adjoining_grammar" title="Tree-adjoining grammar">Tree-adjoining</a></li> <li><a href="/wiki/Context-free_grammar" title="Context-free grammar">Context-free</a></li> <li><a href="/wiki/Deterministic_context-free_grammar" title="Deterministic context-free grammar">Deterministic context-free</a></li> <li><a href="/wiki/Nested_word" title="Nested word">Visibly pushdown</a></li> <li><a href="/wiki/Regular_grammar" title="Regular grammar">Regular</a></li> <li>—</li> <li><a href="/wiki/Non-recursive_grammar" class="mw-redirect" title="Non-recursive grammar">Non-recursive</a></li></ul> </div></td><td class="navbox-list" style="border-left:2px solid #fdfdfd;padding:0px;width:10em;"><div> <ul><li><a href="/wiki/Recursively_enumerable_language" title="Recursively enumerable language">Recursively enumerable</a></li> <li><a href="/wiki/Recursive_language" title="Recursive language">Decidable</a></li> <li><a href="/wiki/Context-sensitive_language" title="Context-sensitive language">Context-sensitive</a></li> <li><span style="white-space:nowrap;">Positive <a href="/wiki/Range_concatenation_language" class="mw-redirect" title="Range concatenation language">range concatenation</a><sup>*</sup></span></li> <li><a href="/wiki/Indexed_language" title="Indexed language">Indexed</a><sup>*</sup></li> <li>—</li> <li><a href="/wiki/Linear_context-free_rewriting_language" class="mw-redirect" title="Linear context-free rewriting language">Linear context-free rewriting language</a></li> <li><a href="/wiki/Tree-adjoining_grammar" title="Tree-adjoining grammar">Tree-adjoining</a></li> <li><a href="/wiki/Context-free_language" title="Context-free language">Context-free</a></li> <li><a href="/wiki/Deterministic_context-free_language" title="Deterministic context-free language">Deterministic context-free</a></li> <li><a href="/wiki/Nested_word" title="Nested word">Visibly pushdown</a></li> <li><a href="/wiki/Regular_language" title="Regular language">Regular</a></li> <li><a href="/wiki/Star-free_language" title="Star-free language">Star-free</a></li> <li><a href="/wiki/Finite_language" class="mw-redirect" title="Finite language">Finite</a></li></ul> </div></td><td class="navbox-list" style="border-left:2px solid #fdfdfd;padding:0px;width:10em;"><div> <ul><li><a href="/wiki/Turing_machine" title="Turing machine">Turing machine</a></li> <li><a href="/wiki/Decider_(Turing_machine)" title="Decider (Turing machine)">Decider</a></li> <li><a href="/wiki/Linear_bounded_automaton" title="Linear bounded automaton">Linear-bounded</a></li> <li><a href="/wiki/PTIME" class="mw-redirect" title="PTIME">PTIME</a> Turing Machine</li> <li><a href="/wiki/Nested_stack_automaton" title="Nested stack automaton">Nested stack</a></li> <li><a href="/wiki/Thread_automaton" title="Thread automaton">Thread automaton</a></li> <li>restricted <a href="/wiki/Tree_stack_automaton" title="Tree stack automaton">Tree stack automaton</a></li> <li><a href="/wiki/Embedded_pushdown_automaton" title="Embedded pushdown automaton">Embedded pushdown</a></li> <li><a href="/wiki/Pushdown_automaton" title="Pushdown automaton">Nondeterministic pushdown</a></li> <li><a href="/wiki/Deterministic_pushdown_automaton" title="Deterministic pushdown automaton">Deterministic pushdown</a></li> <li><a href="/wiki/Nested_word" title="Nested word">Visibly pushdown</a></li> <li><a class="mw-selflink selflink">Finite</a></li> <li><a href="/wiki/Aperiodic_finite_state_automaton" title="Aperiodic finite state automaton">Counter-free (with aperiodic finite monoid)</a></li> <li><a href="/wiki/Deterministic_acyclic_finite_state_automaton" title="Deterministic acyclic finite state automaton">Acyclic finite</a></li></ul> </div></td></tr></tbody></table></div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div><span style="white-space:nowrap;">Each category of languages, except those marked by a <sup>*</sup>, is a <a href="/wiki/Proper_subset" class="mw-redirect" title="Proper subset">proper subset</a> of the category directly above it.</span> <span style="white-space:nowrap;">Any language in each category is generated by a grammar and by an automaton in the category in the same line.</span></div></td></tr></tbody></table></div> <div class="navbox-styles"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236075235"></div><div role="navigation" class="navbox" aria-labelledby="Digital_electronics" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1239400231"><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Digital_electronics" title="Template:Digital electronics"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Digital_electronics" title="Template talk:Digital electronics"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Digital_electronics" title="Special:EditPage/Template:Digital electronics"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Digital_electronics" style="font-size:114%;margin:0 4em"><a href="/wiki/Digital_electronics" title="Digital electronics">Digital electronics</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%;text-align:center;"><a href="/wiki/Electronic_component" title="Electronic component">Components</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Transistor" title="Transistor">Transistor</a></li> <li><a href="/wiki/Resistor" title="Resistor">Resistor</a></li> <li><a href="/wiki/Inductor" title="Inductor">Inductor</a></li> <li><a href="/wiki/Capacitor" title="Capacitor">Capacitor</a></li> <li><a href="/wiki/Printed_electronics" title="Printed electronics">Printed electronics</a></li> <li><a href="/wiki/Printed_circuit_board" title="Printed circuit board">Printed circuit board</a></li> <li><a href="/wiki/Electronic_circuit" title="Electronic circuit">Electronic circuit</a></li> <li><a href="/wiki/Flip-flop_(electronics)" title="Flip-flop (electronics)">Flip-flop</a></li> <li><a href="/wiki/Memory_cell_(computing)" title="Memory cell (computing)">Memory cell</a></li> <li><a href="/wiki/Combinational_logic" title="Combinational logic">Combinational logic</a></li> <li><a href="/wiki/Sequential_logic" title="Sequential logic">Sequential logic</a></li> <li><a href="/wiki/Logic_gate" title="Logic gate">Logic gate</a></li> <li><a href="/wiki/Boolean_circuit" title="Boolean circuit">Boolean circuit</a></li> <li><a href="/wiki/Integrated_circuit" title="Integrated circuit">Integrated circuit</a> (IC)</li> <li><a href="/wiki/Hybrid_integrated_circuit" title="Hybrid integrated circuit">Hybrid integrated circuit</a> (HIC)</li> <li><a href="/wiki/Mixed-signal_integrated_circuit" title="Mixed-signal integrated circuit">Mixed-signal integrated circuit</a></li> <li><a href="/wiki/Three-dimensional_integrated_circuit" title="Three-dimensional integrated circuit">Three-dimensional integrated circuit</a> (3D IC)</li> <li><a href="/wiki/Emitter-coupled_logic" title="Emitter-coupled logic">Emitter-coupled logic</a> (ECL)</li> <li><a href="/wiki/Erasable_programmable_logic_device" class="mw-redirect" title="Erasable programmable logic device">Erasable programmable logic device</a> (EPLD)</li> <li><a href="/wiki/Macrocell_array" title="Macrocell array">Macrocell array</a></li> <li><a href="/wiki/Programmable_logic_array" title="Programmable logic array">Programmable logic array</a> (PLA)</li> <li><a href="/wiki/Programmable_logic_device" title="Programmable logic device">Programmable logic device</a> (PLD)</li> <li><a href="/wiki/Programmable_Array_Logic" title="Programmable Array Logic">Programmable Array Logic</a> (PAL)</li> <li><a href="/wiki/Generic_Array_Logic" title="Generic Array Logic">Generic Array Logic</a> (GAL)</li> <li><a href="/wiki/Complex_programmable_logic_device" title="Complex programmable logic device">Complex programmable logic device</a> (CPLD)</li> <li><a href="/wiki/Field-programmable_gate_array" title="Field-programmable gate array">Field-programmable gate array</a> (FPGA)</li> <li><a href="/wiki/Field-programmable_object_array" title="Field-programmable object array">Field-programmable object array</a> (FPOA)</li> <li><a href="/wiki/Application-specific_integrated_circuit" title="Application-specific integrated circuit">Application-specific integrated circuit</a> (ASIC)</li> <li><a href="/wiki/Tensor_Processing_Unit" title="Tensor Processing Unit">Tensor Processing Unit</a> (TPU)</li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%;text-align:center;">Theory</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Digital_signal" title="Digital signal">Digital signal</a></li> <li><a href="/wiki/Boolean_algebra" title="Boolean algebra">Boolean algebra</a></li> <li><a href="/wiki/Logic_synthesis" title="Logic synthesis">Logic synthesis</a></li> <li><a href="/wiki/Logic_in_computer_science" title="Logic in computer science">Logic in computer science</a></li> <li><a href="/wiki/Computer_architecture" title="Computer architecture">Computer architecture</a></li> <li><a href="/wiki/Digital_signal_(signal_processing)" title="Digital signal (signal processing)">Digital signal</a> <ul><li><a href="/wiki/Digital_signal_processing" title="Digital signal processing">Digital signal processing</a></li></ul></li> <li><a href="/wiki/Circuit_minimization_for_Boolean_functions" class="mw-redirect" title="Circuit minimization for Boolean functions">Circuit minimization</a></li> <li><a href="/wiki/Switching_circuit_theory" title="Switching circuit theory">Switching circuit theory</a></li> <li><a href="/wiki/Gate_equivalent" title="Gate equivalent">Gate equivalent</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%;text-align:center;"><a href="/wiki/Electronics_design" class="mw-redirect" title="Electronics design">Design</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Logic_synthesis" title="Logic synthesis">Logic synthesis</a></li> <li><a href="/wiki/Place_and_route" title="Place and route">Place and route</a> <ul><li><a href="/wiki/Placement_(electronic_design_automation)" title="Placement (electronic design automation)">Placement</a></li> <li><a href="/wiki/Routing_(electronic_design_automation)" title="Routing (electronic design automation)">Routing</a></li></ul></li> <li><a href="/wiki/Transaction-level_modeling" title="Transaction-level modeling">Transaction-level modeling</a></li> <li><a href="/wiki/Register-transfer_level" title="Register-transfer level">Register-transfer level</a> <ul><li><a href="/wiki/Hardware_description_language" title="Hardware description language">Hardware description language</a></li> <li><a href="/wiki/High-level_synthesis" title="High-level synthesis">High-level synthesis</a></li></ul></li> <li><a href="/wiki/Formal_equivalence_checking" title="Formal equivalence checking">Formal equivalence checking</a></li> <li><a href="/wiki/Synchronous_circuit" title="Synchronous circuit">Synchronous logic</a></li> <li><a href="/wiki/Asynchronous_circuit" title="Asynchronous circuit">Asynchronous logic</a></li> <li><a class="mw-selflink selflink">Finite-state machine</a> <ul><li><a href="/wiki/Hierarchical_state_machine" class="mw-redirect" title="Hierarchical state machine">Hierarchical state machine</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%;text-align:center;">Applications</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Computer_hardware" title="Computer hardware">Computer hardware</a> <ul><li><a href="/wiki/Hardware_acceleration" title="Hardware acceleration">Hardware acceleration</a></li></ul></li> <li><a href="/wiki/Digital_audio" title="Digital audio">Digital audio</a> <ul><li><a href="/wiki/Digital_radio" title="Digital radio">radio</a></li></ul></li> <li><a href="/wiki/Digital_photography" title="Digital photography">Digital photography</a></li> <li><a href="/wiki/Telephony#Digital_telephony" title="Telephony">Digital telephone</a></li> <li><a href="/wiki/Digital_video" title="Digital video">Digital video</a> <ul><li><a href="/wiki/Digital_cinematography" title="Digital cinematography">cinematography</a></li> <li><a href="/wiki/Digital_television" title="Digital television">television</a></li></ul></li> <li><a href="/wiki/Electronic_literature" title="Electronic literature">Electronic literature</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%;text-align:center;">Design issues</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Metastability_(electronics)" title="Metastability (electronics)">Metastability</a></li> <li><a href="/wiki/Runt_pulse" title="Runt pulse">Runt pulse</a></li></ul> </div></td></tr></tbody></table></div> <div class="navbox-styles"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236075235"><style data-mw-deduplicate="TemplateStyles:r1038841319">.mw-parser-output .tooltip-dotted{border-bottom:1px dotted;cursor:help}</style></div><div role="navigation" class="navbox authority-control" aria-label="Navbox" style="padding:3px"><table class="nowraplinks hlist navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Help:Authority_control" title="Help:Authority control">Authority control databases</a>: National <span class="mw-valign-text-top noprint" typeof="mw:File/Frameless"><a href="https://www.wikidata.org/wiki/Q176452#identifiers" title="Edit this at Wikidata"><img alt="Edit this at Wikidata" src="//upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/10px-OOjs_UI_icon_edit-ltr-progressive.svg.png" decoding="async" width="10" height="10" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/15px-OOjs_UI_icon_edit-ltr-progressive.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/20px-OOjs_UI_icon_edit-ltr-progressive.svg.png 2x" data-file-width="20" data-file-height="20" /></a></span></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><span class="rt-commentedText tooltip tooltip-dotted" title="konečný automat"><a rel="nofollow" class="external text" href="https://aleph.nkp.cz/F/?func=find-c&local_base=aut&ccl_term=ica=ph210246&CON_LNG=ENG">Czech Republic</a></span></span></li></ul></div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Finite-state_machine&oldid=1246478939">https://en.wikipedia.org/w/index.php?title=Finite-state_machine&oldid=1246478939</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Finite_automata" title="Category:Finite automata">Finite automata</a></li><li><a href="/wiki/Category:Management_cybernetics" title="Category:Management cybernetics">Management cybernetics</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:CS1:_long_volume_value" title="Category:CS1: long volume value">CS1: long volume value</a></li><li><a href="/wiki/Category:All_articles_with_dead_external_links" title="Category:All articles with dead external links">All articles with dead external links</a></li><li><a href="/wiki/Category:Articles_with_dead_external_links_from_October_2017" title="Category:Articles with dead external links from October 2017">Articles with dead external links from October 2017</a></li><li><a href="/wiki/Category:Articles_with_permanently_dead_external_links" title="Category:Articles with permanently dead external links">Articles with permanently dead external links</a></li><li><a href="/wiki/Category:Webarchive_template_wayback_links" title="Category:Webarchive template wayback links">Webarchive template wayback links</a></li><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</a></li><li><a href="/wiki/Category:Use_dmy_dates_from_January_2020" title="Category:Use dmy dates from January 2020">Use dmy dates from January 2020</a></li><li><a href="/wiki/Category:Wikipedia_articles_needing_clarification_from_March_2021" title="Category:Wikipedia articles needing clarification from March 2021">Wikipedia articles needing clarification from March 2021</a></li><li><a href="/wiki/Category:All_articles_with_unsourced_statements" title="Category:All articles with unsourced statements">All articles with unsourced statements</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_March_2021" title="Category:Articles with unsourced statements from March 2021">Articles with unsourced statements from March 2021</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_January_2017" title="Category:Articles with unsourced statements from January 2017">Articles with unsourced statements from January 2017</a></li><li><a href="/wiki/Category:All_articles_that_are_too_technical" title="Category:All articles that are too technical">All articles that are too technical</a></li><li><a href="/wiki/Category:Wikipedia_articles_that_are_too_technical_from_January_2017" title="Category:Wikipedia articles that are too technical from January 2017">Wikipedia articles that are too technical from January 2017</a></li><li><a href="/wiki/Category:All_articles_needing_expert_attention" title="Category:All articles needing expert attention">All articles needing expert attention</a></li><li><a href="/wiki/Category:Articles_needing_expert_attention_from_January_2017" title="Category:Articles needing expert attention from January 2017">Articles needing expert attention from January 2017</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 19 September 2024, at 06:12<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Finite-state_machine&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-f69cdc8f6-68pwz","wgBackendResponseTime":175,"wgPageParseReport":{"limitreport":{"cputime":"0.972","walltime":"1.289","ppvisitednodes":{"value":5828,"limit":1000000},"postexpandincludesize":{"value":138672,"limit":2097152},"templateargumentsize":{"value":6719,"limit":2097152},"expansiondepth":{"value":17,"limit":100},"expensivefunctioncount":{"value":17,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":179866,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 1034.494 1 -total"," 28.44% 294.198 36 Template:Cite_book"," 25.58% 264.590 1 Template:Reflist"," 10.88% 112.565 1 Template:Formal_languages_and_grammars"," 10.47% 108.345 1 Template:Navbox_with_columns"," 9.49% 98.222 1 Template:Short_description"," 8.03% 83.051 6 Template:Fix"," 6.71% 69.449 3 Template:Redirect"," 6.27% 64.825 2 Template:Pagetype"," 4.09% 42.307 1 Template:Authority_control"]},"scribunto":{"limitreport-timeusage":{"value":"0.571","limit":"10.000"},"limitreport-memusage":{"value":7515839,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-f69cdc8f6-67nx9","timestamp":"20241122140337","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Finite-state machine","url":"https:\/\/en.wikipedia.org\/wiki\/Finite-state_machine","sameAs":"http:\/\/www.wikidata.org\/entity\/Q176452","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q176452","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2001-08-01T21:35:22Z","dateModified":"2024-09-19T06:12:29Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/a\/a2\/Automata_theory.svg","headline":"mathematical model of computation; abstract machine that can be in exactly one of a finite number of states at any given time"}</script> </body> </html>