人工智慧/搜尋/窮舉搜尋/有限狀態自動機

使用有限狀態自動機搜尋

在符號字串中搜索模式的一種常用方法是使用 有限狀態自動機，也稱為有限狀態機或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)