关于编译原理:elixir-0084-关于-DFA确定性有限自动机的那些事儿

最近在看 编译原理 这本书，感觉是很棒的入门书（指难度由浅入深深深深）。前两章次要是一些概念性的货色，第三章就开始动真格的，上代码上公式了。不本人实现一下，根本就是看得云里雾里的。所以接下来一段时间可能会不定期地更新一些对于我在 编译原理 这本书里看到的货色的实现的文章。

书本的第三章介绍了 DFA 是如何对字符串进行匹配的，例如，正则表达式 (a|b)*abb 能够转换为以下的 DFA 代码。通过状态机的机制在读取字符时切换以后状态，并依据最初的状态来确定匹配是否胜利。

defmodule DFA do
  
  def init(string) do
    %{
      s: 0,
      chars: String.to_charlist(string)
    }
  end

  def run(%{s: s, chars: [h | t]}) do
    s = move(s, h)
    run(%{s: s, chars: t})
  end
  def run(%{s: s, chars: []}) do
    if s in f() do
      :yes
    else
      :no
    end
  end

  defp move(0, ?a), do: 1
  defp move(0, ?b), do: 0
  defp move(1, ?a), do: 1
  defp move(1, ?b), do: 2
  defp move(2, ?a), do: 1
  defp move(2, ?b), do: 3
  defp move(3, ?a), do: 1
  defp move(3, ?b), do: 0

  defp f(), do: [3]

end

这个 DFA 只会匹配到以 “abb” 结尾的字符串：

DFA.init("ababb")
|> DFA.run()

# :yes

DFA.init("ababa")
|> DFA.run()

# :no

是不是很神奇呢