人工智能/搜索/穷举搜索/有限状态自动机

使用有限状态自动机搜索

在符号字符串中搜索模式的一种常用方法是使用 有限状态自动机，也称为有限状态机或FSM。 FSM 是抽象结构，可以用多种不同的方式实现，但它们都有一些共同的属性。 每个 FSM 都有

• 一组有限的状态
• 接收输入的方式
• 转换，这是由输入触发的从一个状态到另一个状态的路径
• 可选的动作，这些动作根据触发它们的事件类型有几种不同的形式
  • 进入动作在进入特定状态时发生
  • 退出动作在退出特定状态时发生
  • 输入动作仅在机器处于特定状态时接收到特定类型的输入时发生
  • 转换动作在指定的转换期间发生

接受器

当用于字符串中的模式匹配时，FSM 会将字符串的每个连续字符作为输入。 对于简单的子字符串匹配，FSM 将为迄今为止匹配的子字符串中的每个字符数有一个状态。

仅使用是/否响应接受或拒绝输入字符串的有限状态自动机称为 接受器 。 这是一个在字符串包含子字符串“aba”时返回“yes”响应的接受器的 状态图

机器从“空”状态开始，代表空子字符串缓冲区。 “其他”转换代表除“a”或“b”以外的任何字符的输入，因此将机器从空状态中移出的唯一输入是待匹配子字符串的第一个字符“a”。 从那时起，输入将转换为从一个状态到另一个状态的转换。

围绕“aba”的双圆圈表示它是此 FSM 的接受状态，这意味着如果机器在处理完所有输入后处于此状态，则机器将给出“yes”结果。 所有其他状态都是非接受状态，并且在处理结束时将导致“no”结果。

转换器

具有提供输出的动作的 FSM 称为 有限状态转换器。 以下是用 Ruby 编写的转换器示例，它从输入流中剥离 C++/Java 样式的注释

#!/usr/bin/env ruby

# comment_stripper.rb
# 
# Requires Ruby 1.8.7
# 
# Strips C++/Java style comments from an input stream using a finite state
# transducer. Single-line comments begin with two forward slashes ("//") and
# extend to the end of the line. Block comments begin with a slash followed by an
# asterisk ("/*") and end with an asterisk followed by a slash ("*/").
# 
# When run from the command line, performs the transformation on standard input.
# 
# Example:
# 
# cat hello_world.cpp | ruby comment_stripper.rb

class CommentStripper
  def initialize()
    @current_state = :code
  end
  
  def input(c)
    output = INPUT_ACTIONS[c][@current_state] || ''
    @current_state = TRANSITIONS[c][@current_state] || @current_state
    return output
  end
  
  TRANSITIONS = Hash.new do |hash,input|
    # triggered by any characters other than the ones explicitly defined below
    {
      :slash  => :code,
      :star   => :block
    }
  end.merge(
    # overrides the default transitions defined above
    "/" => {
      :code   => :slash,
      :slash  => :line,
      :star   => :code
    },
    "*" => {
      :slash  => :block,
      :block  => :star
    },
    "\n" => {
      :line   => :code,
      :slash  => :code,
      :star   => :block
    }
  )
  
  INPUT_ACTIONS = Hash.new do |hash,input|
    {
      :code   => input,
      :slash  => ("/" + input)
    }
  end.merge(
    "/" => {},
    "*" => {
      :code   => "*"
    },
    "\n" => {
      :code   => "\n",
      :slash  => "/\n",
      :line   => "\n"
    }
  )
end

if $0 == __FILE__
  cs = CommentStripper.new
  $stdin.each_char do |c|
    print cs.input(c)
  end
end

转换和输入动作都在嵌套的哈希表中定义，这些哈希表以输入和状态为键。 input 方法接收输入字符串中的单个字符，执行任何必要的转换到新状态，并根据原始状态返回转换后的字符。 此图显示了在此机器中定义的转换和状态

进一步阅读

• Booth, Taylor L. (1967). Sequential Machines and Automata Theory (1st ed.). New York: John Wiley and Sons, Inc. Library of Congress Card Catalog Number 67-25924. {{cite book}}: Cite has empty unknown parameter: |coauthors= (help)