StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POCode Golf: Finite-state machine!
primarykey
Id
4661818
data
AcceptedAnswerId
4723235
AnswerCount
20
ClosedDate
CommentCount
34
CommunityOwnedDate
2011-01-11T19:38:07.067
CreationDate
2011-01-11T19:38:07.067
FavoriteCount
19
LastActivityDate
2015-04-03T16:40:55.607
LastEditDate
2017-05-23T12:30:36.590
LastEditorUserId
-1
OwnerUserId
51197
ParentId
0
PostTypeId
1
Score
35
ViewCount
7348
LastEditorDisplayName
text
Body
<h2>Finite state machine</h2> <p>A deterministic finite state machine is a simple computation model, widely used as an introduction to automata theory in basic CS courses. It is a simple model, equivalent to regular expression, which determines of a certain input string is <em>Accepted</em> or <em>Rejected</em>. <a href="http://en.wikipedia.org/wiki/Finite-state_machine#Mathematical_model" rel="nofollow noreferrer">Leaving some formalities aside</a>, A run of a finite state machine is composed of:</p> <ol> <li><em>alphabet</em>, a set of characters.</li> <li><em>states</em>, usually visualized as circles. One of the states must be the <em>start state</em>. Some of the states might be <em>accepting</em>, usually visualized as double circles.</li> <li><em>transitions</em>, usually visualized as directed arches between states, are directed links between states associated with an alphabet letter.</li> <li><em>input string</em>, a list of <em>alphabet</em> characters.</li> </ol> <p>A <em>run</em> on the machine begins at the starting state. Each letter of the input string is read; If there is a transition between the current state and another state which corresponds to the letter, the current state is changed to the new state. After the last letter was read, if the current state is an accepting state, the input string is accepted. If the last state was not an accepting state, or a letter had no corresponding arch from a state during the run, the input string is rejected.</p> <p>Note: This short descruption is far from being a full, formal definition of a FSM; <a href="http://en.wikipedia.org/wiki/Finite-state_machine#Mathematical_model" rel="nofollow noreferrer">Wikipedia's fine article</a> is a great introduction to the subject.</p> <h2>Example</h2> <p>For example, the following machine tells if a binary number, read from left to right, has an even number of <code>0</code>s:</p> <p><img src="https://i.stack.imgur.com/fDBWN.png" alt="http://en.wikipedia.org/wiki/Finite-state_machine"></p> <ol> <li>The alphabet is the set <code>{0,1}</code>.</li> <li>The states are S1 and S2.</li> <li>The transitions are <code>(S1, 0) -> S2</code>, <code>(S1, 1) -> S1</code>, <code>(S2, 0) -> S1</code> and <code>(S2, 1) -> S2</code>.</li> <li>The input string is any binary number, including an empty string.</li> </ol> <h2>The rules:</h2> <p>Implement a FSM in a language of your choice. </p> <h3>Input</h3> <p>The FSM should accept the following input:</p> <pre><code><States> List of state, separated by space mark. The first state in the list is the start state. Accepting states begin with a capital letter. <transitions> One or more lines. Each line is a three-tuple: origin state, letter, destination state) <input word> Zero or more characters, followed by a newline. </code></pre> <p>For example, the aforementioned machine with <code>1001010</code> as an input string, would be written as:</p> <pre><code>S1 s2 S1 0 s2 S1 1 S1 s2 0 S1 s2 1 s2 1001010 </code></pre> <h3>Output</h3> <p>The FSM's run, written as <code><State> <letter> -> <state></code>, followed by the final state. The output for the example input would be:</p> <pre><code>S1 1 -> S1 S1 0 -> s2 s2 0 -> S1 S1 1 -> S1 S1 0 -> s2 s2 1 -> s2 s2 0 -> S1 ACCEPT </code></pre> <p>For the empty input <code>''</code>:</p> <pre><code>S1 ACCEPT </code></pre> <p><strong>Note:</strong> Following your comments, the <code>S1</code> line (showing the first state) might be omitted, and the following output is also acceptable:</p> <pre><code>ACCEPT </code></pre> <p>For <code>101</code>:</p> <pre><code>S1 1 -> S1 S1 0 -> s2 s2 1 -> s2 REJECT </code></pre> <p>For <code>'10X'</code>:</p> <pre><code>S1 1 -> S1 S1 0 -> s2 s2 X REJECT </code></pre> <h3>Prize</h3> <p>A 250 rep bounty will be given to the shortest solution.</p> <h2>Reference implementation</h2> <p>A reference Python implementation is available <a href="http://friendpaste.com/58v7LrH0bGqC4b23QjYdDv" rel="nofollow noreferrer">here</a>. Note that output requirements have been relaxed for empty-string input.</p> <h1>Addendum</h1> <h2>Output format</h2> <p>Following popular demand, the following output is also acceptable for empty input string:</p> <pre><code>ACCEPT </code></pre> <p>or</p> <pre><code>REJECT </code></pre> <p>Without the first state written in the previous line.</p> <h2>State names</h2> <p>Valid state names are an English letter followed by any number of letters, <code>_</code> and digits, much like variable names, e.g. <code>State1</code>, <code>state0</code>, <code>STATE_0</code>.</p> <h2>Input format</h2> <p>Like most code golfs, you can assume your input is correct.</p> <h2>Summary of answers:</h2> <ul> <li>Cobol - <a href="https://stackoverflow.com/questions/4661818/code-golf-finite-state-machine/4662814#4662814">4078 characters</a></li> <li>Python - <a href="https://stackoverflow.com/questions/4661818/code-golf-finite-state-machine/4666506#4666506">171 characters</a>, <a href="https://stackoverflow.com/questions/4661818/code-golf-finite-state-machine/4662032#4662032">568 characters</a>, <a href="https://stackoverflow.com/questions/4661818/code-golf-finite-state-machine/4743454#4743454">203 characters</a>, <a href="https://stackoverflow.com/questions/4661818/code-golf-finite-state-machine/4663124#4663124">218 characters</a>, <a href="https://stackoverflow.com/questions/4661818/code-golf-finite-state-machine/4662150#4662150">269 characters</a></li> <li>sed - <a href="https://stackoverflow.com/questions/4661818/code-golf-finite-state-machine/4687779#4687779">137 characters</a></li> <li>ruby - <a href="https://stackoverflow.com/questions/4661818/code-golf-finite-state-machine/4723235#4723235">145 characters</a>, <a href="https://stackoverflow.com/questions/4661818/code-golf-finite-state-machine/4666863#4666863">183 characters</a></li> <li>Haskell - <a href="https://stackoverflow.com/questions/4661818/code-golf-finite-state-machine/4666075#4666075">192 characters</a>, <a href="https://stackoverflow.com/questions/4661818/code-golf-finite-state-machine/4708713#4708713">189 characters</a></li> <li>LISP - <a href="https://stackoverflow.com/questions/4661818/code-golf-finite-state-machine/4728522#4728522">725 characters</a></li> <li>Perl - <a href="https://stackoverflow.com/questions/4661818/code-golf-finite-state-machine/4709167#4709167">184 characters</a></li> <li>Bash - <a href="https://stackoverflow.com/questions/4661818/code-golf-finite-state-machine/4767994#4767994">184 characters</a></li> <li>Rexx - <a href="https://stackoverflow.com/questions/4661818/code-golf-finite-state-machine/4702588#4702588">205 characters</a></li> <li>Lua - <a href="https://stackoverflow.com/questions/4661818/code-golf-finite-state-machine/4748356#4748356">356 characters</a></li> <li>F# - <a href="https://stackoverflow.com/questions/4661818/code-golf-finite-state-machine/4766246#4766246">420 characters</a></li> <li>C# - <a href="https://stackoverflow.com/questions/4661818/code-golf-finite-state-machine/4753598#4753598">356 characters</a></li> <li><a href="http://www.catb.org/~esr/mixal/" rel="nofollow noreferrer">Mixal</a> - <a href="https://stackoverflow.com/questions/4661818/code-golf-finite-state-machine/4788780#4788780">898 characters</a></li> </ul> <p>The <a href="https://stackoverflow.com/questions/4661818/code-golf-finite-state-machine/4687779#4687779"><code>sed</code> 137 solution</a> is the shortest, <a href="https://stackoverflow.com/questions/4661818/code-golf-finite-state-machine/4723235#4723235">ruby 145</a> is #2. Currently, I can't get the sed solution to work:</p> <pre><code>cat test.fsm | sed -r solution.sed sed -r solution.sed test.fsm </code></pre> <p>both gave me:</p> <pre><code>sed: -e expression #1, char 12: unterminated `s' command </code></pre> <p>so unless It there are clarifications the bounty goes to the ruby solution.</p>
Tags
<python><language-agnostic><code-golf><finite-state-machine>
Title
Code Golf: Finite-state machine!
singulars
PostAcceptedAnswerId
1. PO
  singulars
  PostTypePostTypeId
  PTAnswer
PostParentId
1. This table or related slice is empty.
PostTypePostTypeId
1. PTQuestion
UserLastEditorUserId
1. USCommunity
UserOwnerUserId
1. USAdam Matan
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. PL
  singulars
  LinkTypeLinkTypeId
  LTLinked
2. PL
  singulars
  LinkTypeLinkTypeId
  LTLinked
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. PO
  singulars
  PostTypePostTypeId
  PTAnswer
2. PO
  singulars
  PostTypePostTypeId
  PTAnswer
3. PO
  singulars
  PostTypePostTypeId
  PTAnswer
VotesPostIdCreationDate
1. VO
  singulars
  PostPostId
  POCode Golf: Finite-state machine!
  UserUserId
  This table or related slice is empty.
  VoteTypeVoteTypeId
  VTUpMod
2. VO
  singulars
  PostPostId
  POCode Golf: Finite-state machine!
  UserUserId
  This table or related slice is empty.
  VoteTypeVoteTypeId
  VTUpMod
3. VO
  singulars
  PostPostId
  POCode Golf: Finite-state machine!
  UserUserId
  This table or related slice is empty.
  VoteTypeVoteTypeId
  VTDownMod
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.