首页 / 问题 / 正文

代码高尔夫：有限状态机！

35 投票
20 回答
10313 浏览
提问于 2025-04-16 09:47

有限状态机

确定性有限状态机是一种简单的计算模型，通常用作计算机科学基础课程中自动机理论的入门。它是一个简单的模型，和正则表达式等价，用来判断某个输入字符串是被接受还是拒绝。抛开一些正式的定义不谈，有限状态机的运行由以下几个部分组成：

  1. 字母表，一组字符。
  2. 状态，通常用圆圈表示。必须有一个状态是起始状态，有些状态可能是接受状态，通常用双圆圈表示。
  3. 转换，通常用有向箭头表示状态之间的连接，是与字母表字母相关的状态之间的有向链接。
  4. 输入字符串，一系列字母表中的字符。

在机器上进行运行时，从起始状态开始。读取输入字符串的每个字母；如果当前状态和另一个状态之间有对应于该字母的转换，则当前状态会变为新状态。在读取完最后一个字母后，如果当前状态是接受状态，则输入字符串被接受。如果最后的状态不是接受状态，或者在运行过程中某个字母没有对应的转换，输入字符串就会被拒绝。

注意：这个简短的描述远不是有限状态机的完整正式定义；维基百科的这篇文章是一个很好的入门资料。

示例

例如，下面的机器可以判断一个从左到右读取的二进制数字中有多少个0，是否是偶数：

http://en.wikipedia.org/wiki/Finite-state_machine

  1. 字母表是{0,1}。
  2. 状态是S1和S2。
  3. 转换是(S1, 0) -> S2、(S1, 1) -> S1、(S2, 0) -> S1和(S2, 1) -> S2。
  4. 输入字符串可以是任何二进制数字，包括空字符串。

规则：

用你选择的语言实现一个有限状态机。

输入

有限状态机应该接受以下输入：

<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

输出

有限状态机的运行结果，格式为<状态> <字母> -> <状态>，后面跟着最终状态。对于示例输入，输出将是：

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声望的奖励。

参考实现

可以在这里找到一个参考的Python实现。请注意，对于空字符串输入，输出要求已经放宽。

附录

输出格式

根据大家的需求，对于空输入字符串，以下输出也是可以接受的：

ACCEPT

或者

REJECT

不需要在前一行写出第一个状态。

状态名称

有效的状态名称是一个英文字母后面跟着任意数量的字母、_和数字，类似于变量名，例如State1、state0、STATE_0。

输入格式

像大多数代码挑战一样，你可以假设你的输入是正确的。

答案总结：

最短的解决方案是sed 137个字符的方案，第二短的是ruby 145个字符。目前，我无法让sed的解决方案正常工作：

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

这两个都给了我：

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

所以除非有进一步的说明，否则奖励将给予ruby的解决方案。

状态转换 自动机理论 字母表 有限状态机 输入字符串 确定性有限状态机 接受状态 计算模型

20 个回答

21

今天我有点怀旧，想用IBM企业级Cobol这门语言来完成这个任务 - 字符数 2462 4078（抱歉，这是从一个屏幕设备上复制过来的，后面的空格是个悲剧的副作用）：

 Identification Division.               
 Program-ID. FSM.                       
 Environment Division.                  
 Data Division.                         
 Working-Storage Section.               

 01 FSM-Storage.                        

*> The current state                    
   05 Start-State      Pic X(2).        
   05 Next-State       Pic X(2).        

*> List of valid states                 
   05 FSM-State-Cnt    Pic 9.           
   05 FSM-States       Occurs 9         
                       Pic X(2).        

*> List of valid transitions            
   05 FSM-Trans-Cnt    Pic 999.         
   05 FSM-Trans        Occurs 999.      
     10 Trans-Start    Pic X(2).        
     10 Trans-Char     Pic X.           
     10 Trans-End      Pic X(2).        

*> Input                                
   05 In-Buff          Pic X(72).      

*> Some work fields                     
   05 II               Pic s9(8) binary.
   05 JJ               Pic s9(8) binary.

   05 Wk-Start         Pic X(2).        
   05 Wk-Char          Pic X.           
   05 Wk-End           Pic X(2).        
   05 Wk-Cnt           Pic 999.         

   05                  Pic X value ' '. 
     88 Valid-Input        value 'V'.   

   05                  Pic X value ' '.                 
     88 Valid-State        value 'V'.                   

   05                  Pic X value ' '.                 
     88 End-Of-States      value 'E'.                   

   05                  Pic X value ' '.                 
     88 Trans-Not-Found    value ' '.                   
     88 Trans-Found        value 'T'.                   


 Linkage Section.                                       

 01 The-Char-Area.                                      
   05 The-Char         Pic X.                           
     88 End-Of-Input       value x'13'.                 
   05 The-Next-Char    Pic X.                           

 Procedure Division.                                    

      Perform Load-States                               
      Perform Load-Transitions                          
      Perform Load-Input                                
      Perform Process-Input                             

      Goback.                                           

*> Run the machine...                                   
 Process-Input.                                         

      Move FSM-States (1) to Start-State                
      Set address of The-Char-Area to address of In-Buff

      Perform until End-Of-Input                        

        Perform Get-Next-State                          
        Set address of The-Char-Area to address of The-Next-Char

        Move Next-State to Start-State                          

      End-Perform                                               

      If Start-State (1:1) is Alphabetic-Lower                  
        Display 'REJECT'                                        
      Else                                                      
        Display 'ACCEPT'                                        
      End-If                                                    

      Exit.                                                     

*> Look up the first valid transition...                        
 Get-Next-State.                                                

      Set Trans-Not-Found to true                               
      Perform varying II from 1 by 1                            
        until (II > FSM-State-Cnt)                              
           or Trans-Found                                       

        If Start-State = Trans-Start (II)                       
          and The-Char = Trans-Char (II)                        

          Move Trans-End (II) to Next-State                     
          Set Trans-Found to true                               

        End-If                                                  

      End-Perform                                               
      Display Start-State ' ' The-Char ' -> ' Next-State        

      Exit.                                                     

*> Read the states in...                                        
 Load-States.                                                   

      Move low-values to In-Buff                         
      Accept In-Buff from SYSIN                          

      Move 0 to FSM-State-Cnt                            
      Unstring In-Buff                                   
        delimited by ' '                                 
        into FSM-States (1) FSM-States (2) FSM-States (3)
             FSM-States (4) FSM-States (5) FSM-States (6)
             FSM-States (7) FSM-States (8) FSM-States (9)
        count in FSM-State-Cnt                           
      End-Unstring                                       

      Exit.                                              

*> Read the transitions in...                            
 Load-Transitions.                                       

      Move low-values to In-Buff                         
      Accept In-Buff from SYSIN                          

      Perform varying II from 1 by 1                     
        until End-Of-States                              

        Move 0 to Wk-Cnt                                 
        Unstring In-Buff                                 
          delimited by ' '                               
          into Wk-Start Wk-Char Wk-End                   
          count in Wk-Cnt                                
        End-Unstring                                     

        If Wk-Cnt = 3                                    

          Add 1 to FSM-Trans-Cnt                         
          Move Wk-Start to Trans-Start (FSM-Trans-Cnt)   
          Move Wk-Char  to Trans-Char  (FSM-Trans-Cnt)   
          Move Wk-End   to Trans-End   (FSM-Trans-Cnt)   

          Move low-values to In-Buff                     
          Accept In-Buff from SYSIN                           

        Else                                                  

          Set End-Of-States to true                           

        End-If                                                

      End-Perform                                             

      Exit.                                                   

*> Fix input so it has newlines...the joys of mainframes      
 Load-Input.                                                  

      Perform varying II from length of In-Buff by -1         
        until Valid-Input                                     

        If In-Buff (II:1) = ' ' or In-Buff (II:1) = low-values
          Move x'13' to In-Buff (II:1)                        
        Else                                                  
          Set Valid-Input to true                             
        End-If                                                

      End-Perform                                             

      Exit.                                                   

  End Program FSM.
回答于 2025-04-16 由 Python大师
分享 举报
23

Python 2.7+, 201 192 187 181 179 175 171 个字符

补充说明：在问题的要求放宽后（不需要在输入为空时输出状态行），这里的新代码明显更短。如果你使用的版本低于2.7，就没有字典推导式这个功能，所以可以用dict((c+o,s)for o,c,s in i[1:-1])来代替{c+o:s for o,c,s in i[1:-1]}，这样会多花5个字符。

import sys
i=map(str.split,sys.stdin)
s=i[0][0]
for c in''.join(i[-1]):
    if s:o=s;s={c+o:s for o,c,s in i[1:-1]}.get(c+s,());print o,c,'->',s
print'ARCECJEEPCTT'[s>'Z'::2]

这是它的测试输出：

# for empty input
ACCEPT

# for input '1001010'
S1 1  ->  S1
S1 0  ->  s2
s2 0  ->  S1
S1 1  ->  S1
S1 0  ->  s2
s2 1  ->  s2
s2 0  ->  S1
ACCEPT

# for input '101'
S1 1  ->  S1
S1 0  ->  s2
s2 1  ->  s2
REJECT

# for input '10X'
S1 1  ->  S1
S1 0  ->  s2
s2 X  ->  ()
REJECT

# for input 'X10'
S1 X  ->  ()
REJECT

之前的版本（长度201）：

import sys
i=list(sys.stdin)
s=i[0].split()[0]
t={}
for r in i[1:-1]:a,b,c=r.split();t[a,b]=c
try:
    for c in i[-1]:print s,c.strip(),;s=t[s,c];print' ->',s
except:print('ACCEPT','REJECT')[s>'Z'or' '<c]

在有人指责我之前，我想先道个歉：这段代码的行为与最初的规范稍有不同——这是根据问题评论的讨论得出的。这是我为讨论提供的示例。

补充说明：虽然我喜欢把接受/拒绝的结果和最终状态放在同一行，但可以把它单独放在一行（例如，想象一下结果要被一个只关心最后一行是接受还是拒绝的简单脚本解析），只需在最后的print前加上'\n'+（增加5个字符）即可。

示例输出：

# for empty input
S1  ACCEPT

# for input '1001010'
S1 1  -> S1
S1 0  -> s2
s2 0  -> S1
S1 1  -> S1
S1 0  -> s2
s2 1  -> s2
s2 0  -> S1
S1  ACCEPT

# for input '101'
S1 1  -> S1
S1 0  -> s2
s2 1  -> s2
s2  REJECT

# for input '10X'
S1 1  -> S1
S1 0  -> s2
s2 X REJECT

# for input 'X10'
S1 X REJECT
回答于 2025-04-16 由 Python大师
分享 举报
8

Ruby 1.9.2 - 178 190 182 177 153 161 158 154 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
回答于 2025-04-16 由 Python大师
分享 举报

撰写回答