Code Golf:有限状态机！ [英] Code Golf: Finite-state machine!

问题描述

有限状态机

确定性有限状态机是一种简单的计算模型，被广泛用作基础CS课程中自动机理论的入门.这是一个简单的模型，等效于正则表达式，它确定某个输入字符串为 Accepted 或 Rejected . 除了一些形式，有限状态机的运行由以下部分组成:

1. 字母，一组字符.
2. 状态，通常可视化为圆圈.状态之一必须是开始状态.有些状态可能是接受，通常显示为双圆圈.
3. 过渡通常可视化为状态之间的有向弓，是与字母相关联的状态之间的有向链接.
4. 输入字符串，字母字符列表.

计算机上的 run 从启动状态开始.读取输入字符串的每个字母；如果当前状态和对应于字母的另一个状态之间存在过渡，则当前状态将更改为新状态.读取最后一个字母后，如果当前状态为接受状态，则接受输入字符串.如果最后一个状态不是接受状态，或者在运行过程中某个字母没有来自该状态的相应拱形，则输入字符串将被拒绝.

注意:这种短暂的破坏远不是FSM的完整，正式的定义. 维基百科的精美文章是对该主题的出色介绍.

示例

例如，下面的机器告诉从左到右读取的二进制数是否具有偶数0 s:

1. 字母是集合{0,1}.
2. 状态为S1和S2.
3. 过渡是(S1, 0) -> S2，(S1, 1) -> S1，(S2, 0) -> S1和(S2, 1) -> S2.
4. 输入字符串是任何二进制数字，包括一个空字符串.

规则:

以您选择的语言实施FSM.

输入

FSM应该接受以下输入:

<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.

例如，上述以1001010作为输入字符串的机器将写为:

S1 s2
S1 0 s2
S1 1 S1
s2 0 S1
s2 1 s2
1001010

输出

FSM的运行，写为<State> <letter> -> <state>，后跟最终状态.示例输入的输出为:

S1 1 -> S1
S1 0 -> s2
s2 0 -> S1
S1 1 -> S1
S1 0 -> s2
s2 1 -> s2
s2 0 -> S1
ACCEPT

对于空输入'':

S1
ACCEPT

注意:在您发表评论后，S1行(显示第一个状态)可能会被省略，并且以下输出也是可以接受的:

ACCEPT

对于101:

S1 1 -> S1
S1 0 -> s2
s2 1 -> s2
REJECT

对于'10X':

S1 1 -> S1
S1 0 -> s2
s2 X
REJECT

奖赏

最短的解决方案将获得250 rep赏金.

参考实现

可在此处获得参考Python实现.请注意，对于空字符串输入，已经放宽了输出要求.

附录

输出格式

遵循流行的需求，对于空的输入字符串，以下输出也是可接受的:

ACCEPT

或

REJECT

没有在上一行中写入的第一个状态.

州名

有效状态名称是英文字母，后跟任意数量的字母，_和数字，非常类似于变量名，例如. State1，state0，STATE_0.

输入格式

就像大多数代码高尔夫球一样，您可以假设您的输入正确.

答案摘要:

• Cobol- 4078个字符
• Python- 171个字符， 203个字符， 269个字符
• sed- 137个字符
• ruby​​- 145个字符， 192个字符， 725个字符
• Perl- 184个字符
• 重击- 184个字符
• Rexx- 205个字符
• Lua- 356个字符
• F#- 420个字符
• C#- 356个字符
• 混合- sed 137解决方案是最短的 ruby​​ 145 是#2.目前，我无法使用sed解决方案:

  cat test.fsm | sed -r solution.sed
  sed -r solution.sed test.fsm
  

  都给了我

  sed: -e expression #1, char 12: unterminated `s' command
  

  因此，除非有明确说明，否则悬赏金将用于红宝石解决方案.

  解决方案

  Ruby 1.9.2- 178190182177177153161158154 145个字符

  h={}
  o=s=p
  $<.map{|l|o,b,c=l.split;h[[o,b]]=c;s||=o}
  o.chars{|c|puts s+' '+c+((s=h[[s,c]])?' -> '+s :'')}rescue 0
  puts s&&s<'['?:ACCEPT: :REJECT
  

  测试脚本

  [
    "S1 s2
  S1 0 s2
  S1 1 S1
  s2 0 S1
  s2 1 s2
  1001010",
    "S1 s2
  S1 0 s2
  S1 1 S1
  s2 0 S1
  s2 1 s2
  101",
    "S1 s2
  S1 0 s2
  S1 1 S1
  s2 0 S1
  s2 1 s2
  ",
    "S1 s2
  S1 0 s2
  S1 1 S1
  s2 0 S1
  s2 1 s2
  10X"
  ].each do |b|
    puts "------"
    puts "Input:"
    puts b
    puts
    puts "Output:"
    puts `echo "#{b}" | ruby fsm-golf.rb`
    puts "------"
  end
  

  输出

  所有输入均始于:

  S1 s2
  S1 0 s2
  S1 1 S1
  s2 0 S1
  s2 1 s2
  

  ---

  Input: '1001010'
  Output:
  S1 1 -> S1
  S1 0 -> s2
  s2 0 -> S1
  S1 1 -> S1
  S1 0 -> s2
  s2 1 -> s2
  s2 0 -> S1
  ACCEPT
  
  Input: '101'
  Output:
  S1 1 -> S1
  S1 0 -> s2
  s2 1 -> s2
  REJECT
  
  Input: 'X10'
  Output:
  S1 X
  REJECT
  
  Input: ''
  Output:
  ACCEPT
  
  Input: '10X'
  Output:
  S1 1 -> S1
  S1 0 -> s2
  s2 X
  REJECT
  

  Finite state machine

  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 Accepted or Rejected. Leaving some formalities aside, A run of a finite state machine is composed of:

  1. alphabet, a set of characters.
  2. states, usually visualized as circles. One of the states must be the start state. Some of the states might be accepting, usually visualized as double circles.
  3. transitions, usually visualized as directed arches between states, are directed links between states associated with an alphabet letter.
  4. input string, a list of alphabet characters.

  A run 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.

  Note: This short descruption is far from being a full, formal definition of a FSM; Wikipedia's fine article is a great introduction to the subject.

  Example

  For example, the following machine tells if a binary number, read from left to right, has an even number of 0s:

  1. The alphabet is the set {0,1}.
  2. The states are S1 and S2.
  3. The transitions are (S1, 0) -> S2, (S1, 1) -> S1, (S2, 0) -> S1 and (S2, 1) -> S2.
  4. The input string is any binary number, including an empty string.

  The rules:

  Implement a FSM in a language of your choice.

  Input

  The FSM should accept the following input:

  <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.
  

  For example, the aforementioned machine with 1001010 as an input string, would be written as:

  S1 s2
  S1 0 s2
  S1 1 S1
  s2 0 S1
  s2 1 s2
  1001010
  

  Output

  The FSM's run, written as <State> <letter> -> <state>, followed by the final state. The output for the example input would be:

  S1 1 -> S1
  S1 0 -> s2
  s2 0 -> S1
  S1 1 -> S1
  S1 0 -> s2
  s2 1 -> s2
  s2 0 -> S1
  ACCEPT
  

  For the empty input '':

  S1
  ACCEPT
  

  Note: Following your comments, the S1 line (showing the first state) might be omitted, and the following output is also acceptable:

  ACCEPT
  

  For 101:

  S1 1 -> S1
  S1 0 -> s2
  s2 1 -> s2
  REJECT
  

  For '10X':

  S1 1 -> S1
  S1 0 -> s2
  s2 X
  REJECT
  

  Prize

  A 250 rep bounty will be given to the shortest solution.

  Reference implementation

  A reference Python implementation is available here. Note that output requirements have been relaxed for empty-string input.

  Addendum

  Output format

  Following popular demand, the following output is also acceptable for empty input string:

  ACCEPT
  

  or

  REJECT
  

  Without the first state written in the previous line.

  State names

  Valid state names are an English letter followed by any number of letters, _ and digits, much like variable names, e.g. State1, state0, STATE_0.

  Input format

  Like most code golfs, you can assume your input is correct.

  Summary of answers:

  • Cobol - 4078 characters
  • Python - 171 characters, 568 characters, 203 characters, 218 characters, 269 characters
  • sed - 137 characters
  • ruby - 145 characters, 183 characters
  • Haskell - 192 characters, 189 characters
  • LISP - 725 characters
  • Perl - 184 characters
  • Bash - 184 characters
  • Rexx - 205 characters
  • Lua - 356 characters
  • F# - 420 characters
  • C# - 356 characters
  • Mixal - 898 characters

  The sed 137 solution is the shortest, ruby 145 is #2. Currently, I can't get the sed solution to work:

  cat test.fsm | sed -r solution.sed
  sed -r solution.sed test.fsm
  

  both gave me:

  sed: -e expression #1, char 12: unterminated `s' command
  

  so unless It there are clarifications the bounty goes to the ruby solution.

  解决方案

  Ruby 1.9.2 - 178 190 182 177 153 161 158 154 145 characters

  h={}
  o=s=p
  $<.map{|l|o,b,c=l.split;h[[o,b]]=c;s||=o}
  o.chars{|c|puts s+' '+c+((s=h[[s,c]])?' -> '+s :'')}rescue 0
  puts s&&s<'['?:ACCEPT: :REJECT
  

  Testing Script

  [
    "S1 s2
  S1 0 s2
  S1 1 S1
  s2 0 S1
  s2 1 s2
  1001010",
    "S1 s2
  S1 0 s2
  S1 1 S1
  s2 0 S1
  s2 1 s2
  101",
    "S1 s2
  S1 0 s2
  S1 1 S1
  s2 0 S1
  s2 1 s2
  ",
    "S1 s2
  S1 0 s2
  S1 1 S1
  s2 0 S1
  s2 1 s2
  10X"
  ].each do |b|
    puts "------"
    puts "Input:"
    puts b
    puts
    puts "Output:"
    puts `echo "#{b}" | ruby fsm-golf.rb`
    puts "------"
  end
  

  Outputs

  All input starts with:

  S1 s2
  S1 0 s2
  S1 1 S1
  s2 0 S1
  s2 1 s2
  

  ---

  Input: '1001010'
  Output:
  S1 1 -> S1
  S1 0 -> s2
  s2 0 -> S1
  S1 1 -> S1
  S1 0 -> s2
  s2 1 -> s2
  s2 0 -> S1
  ACCEPT
  
  Input: '101'
  Output:
  S1 1 -> S1
  S1 0 -> s2
  s2 1 -> s2
  REJECT
  
  Input: 'X10'
  Output:
  S1 X
  REJECT
  
  Input: ''
  Output:
  ACCEPT
  
  Input: '10X'
  Output:
  S1 1 -> S1
  S1 0 -> s2
  s2 X
  REJECT
  

  这篇关于Code Golf:有限状态机！的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！