Ruby のオートマトン学習ライブラリ Lernen を試してみた

はじめに

RubyKaigi 2025 に参加しました！

その中の「Make Parsers Compatible Using Automata Learning」というセッションでは、オートマトン学習の説明と、それを実装したライブラリ「Lernen」を実装して Prism と parse.y の互換性の問題を発見したという話が面白かったです。

そこで、このライブラリを実際に使って試してみようと思います。

オートマトン学習については、上記スライドの内容が非常に分かりやすいので、ここでは割愛します。

Lernen

Lernen は、先ほどのスライドで紹介されていた、オートマトン学習のための Ruby ライブラリです。

まずは簡単な例で使ってみます。

簡単な例でのオートマトン学習

「a が連続で2つ以上含まれる文字列は受理し、それ以外は拒否する」といったシンプルな条件を学習させてみます。

require "lernen"

alphabet = %w[a b]

automaton = Lernen.learn(alphabet:) do |word|
  word.join.include?("aa")
end

puts automaton.to_mermaid

alphabet には使用する文字集合を指定します。
また、ブロック内では word (文字の配列) を受け入れるかどうかを判定して返します。

to_mermaid を使うと、でオートマトンが mermaid 記法で出力されます。
出力された図を見てみます。

2 から 2 への遷移には a と b の両方があるはずですが、mermaid のバグなのか、片方しか表示されていないようです。

to_mermaid の出力結果

flowchart TD
  0(("0"))
  1(("1"))
  2((("2")))

  0 -- "#quot;a#quot;" --> 1
  0 -- "#quot;b#quot;" --> 0
  1 -- "#quot;a#quot;" --> 2
  1 -- "#quot;b#quot;" --> 0
  2 -- "#quot;a#quot;" --> 2
  2 -- "#quot;b#quot;" --> 2

この図から、意図した通りに学習できていそうなことが分かります。

互換性の検証

今度は、2種類のコードが互換かどうかを、学習させたオートマトンを利用して検証してみます。

「文字列が ababa... のように交互になっているか」を判定する2種類のメソッドを用意します。

def regex_match?(string)
  string.match?(/\Aa(ba)*\z/)
end

def condition_match?(string)
  return false if string.empty?

  string.chars.each_with_index.all? do |char, index|
    if index.even?
      char == "a"
    else
      char == "b"
    end
  end
end

人の目では明らかかもしれませんが、regex_match? は b で終わるパターンを許容していないのに対し、condition_match? は最後の文字が a でも b でも許容されるようになっています。

これらを実際に学習させてみます。

alphabet = %w[a b]

regex_automaton = Lernen.learn(alphabet:) do |word|
  regex_match?(word.join)
end

condition_automaton = Lernen.learn(alphabet:) do |word|
  condition_match?(word.join)
end

これらを学習した結果のオートマトンは以下のようになりました。

明らかに違うことが、視覚的にも分かります。
では、どのような入力で両者が異なる結果を返すのか、を調べてみます。

sep_word = Lernen::Automaton::DFA.find_separating_word(alphabet, regex_automaton, condition_automaton)

上記コードを実行すると、この sep_word には "ab" が入っていました。
実際に試してみると、

regex_match?("ab")     # => false
condition_match?("ab") # => true

となり、違いが確認できました。

では、正規表現の方を修正してみます。

def regex_match?(string)
  string.match?(/\Aa(ba)*b?\z/)
end

先程のコードに b? を追加しただけですが、これで両者が同じ意味になるはずです。

これを再度学習させて、オートマトンを見てみると、

このように、両者のオートマトンが一致していることが確認できます。
また、find_separating_word を使っても nil が返ってきて、差異のないことが分かります。

おわりに

オートマトン学習という考え方は、セッションを聞くまで全く知らなかったのですが、パーサーからオートマトンが得られるということには、とても驚きました。
また、それが実際にバグの発見に役立ったというのも、本当に素晴らしいことだと感じました。
今後の進展がとても楽しみです。