tkykmw code

学びたいことを学ぶ

アンダースタンディング コンピュテーション3章のNFA/DFAをGraphvizでビジュアル化

せっかく正規表現→NFA→DFAと変換できるようになったんだから、グラフ図(状態遷移図)で見たいよね、というわけで定番のGraphvizを使ってビジュアル化してみた。

f:id:tkykmw:20180812132423p:plain

Graphviz用のRubyライブラリはいくつも存在するようだが、どれも用途に合わなかったので、自作した。次のような要件が重要。

  • プログラムから動的に操作できること
  • 同じノードの組み合わせに対して複数のエッジを(簡単に)引けること
  • Set 等、任意のRubyオブジェクトを(簡単に)ノードとして追加できること

コードはgistに置いておく。名前は Dotr とした。3番目の要件を満たすために、 #hash の値をノードidに使用している。

Minimal wrapper for Graphviz dot language · GitHub

NFA/DFAをdotに変換する FaVisualizer はこんな感じ。

require_relative './dotr'
require 'open3'

class FaVisualizer
  attr_reader :dotr

  def initialize(fa_design)
    @fa_design = fa_design
    @dotr = Dotr.digraph
    @dotr.attrs(:graph, rankdir: :LR)
    @dotr.attrs(:node, shape: :circle, style: :filled)
    setup_graph
  end

  def image(type = :png)
    stdout, stderr, status = Open3.capture3("dot -T#{type}", stdin_data: dotr.to_s)
    stdout
  end

  private

  def state_label(state)
    case state
    when Set
      if state.empty?
        'none'
      else
        state.to_a.sort.map(&:to_s).join(',')
      end
    else
      state.to_s
    end
  end

  def setup_graph
    rules = @fa_design.rulebook.rules
    rules.flat_map {|rule| [rule.state, rule.next_state] }.uniq.each do |state|
      attrs = { label: state_label(state) }
      if @fa_design.accept_states.include?(state)
        attrs[:shape] = :doublecircle
      end
      if @fa_design.start_state == state
        attrs[:fillcolor] = :powderblue
      end
      @dotr.node(state, **attrs)
    end

    rules.group_by {|rule| rule.character.nil? ? :free : :normal }.each do |move_type, rules|
      if move_type == :free
        add_free_move_edges(rules)
      else
        add_normal_edges(rules)
      end
    end
  end

  def add_normal_edges(rules)
    rules.group_by {|rule| [rule.state, rule.next_state] }.each do |((from, to), rules)|
      @dotr.edge(from, to, label: rules.map(&:character).join(',') )
    end
  end

  def add_free_move_edges(rules)
    rules.each do |rule|
      @dotr.edge(rule.state, rule.next_state, label: ' ', style: :dotted)
    end
  end
end

これでPNGバイナリを出力できる。

design = MyReg::Parser.parse(string).to_nfa_design
puts FaVisualizer.new(design).image

いくつか正規表現をNFA/DFAにしたグラフ図を載せておく。青丸が開始状態、◎が受理状態。

正規表現の状態に数字を割り当てるために、NFA側のコードを変更した)

連結 ab

f:id:tkykmw:20180812132731p:plain
NFA
f:id:tkykmw:20180812132545p:plain
DFA

選択 a|b

f:id:tkykmw:20180812132525p:plain
NFA
f:id:tkykmw:20180812132520p:plain
DFA

繰り返し a*

f:id:tkykmw:20180812132747p:plain
NFA
f:id:tkykmw:20180812132734p:plain
DFA

複雑な例1 (a|b)*aa*

f:id:tkykmw:20180812132531p:plain
NFA
f:id:tkykmw:20180812132530p:plain
DFA

複雑な例2 (a*b)*

f:id:tkykmw:20180812132540p:plain
NFA
f:id:tkykmw:20180812132535p:plain
DFA

こうして見比べると、DFAの方がはるかに理解しやすい。一見複雑に見えても簡単に処理を追える。

本当は状態遷移していく過程もビジュアル化してみたいが……もとのコードにかなり手を入れないと難しそうだ。