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

## はじめに

RubyKaigi 2025 に参加しました！

https://rubykaigi.org/2025/

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

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

https://rubykaigi.org/2025/presentations/makenowjust.html#day1

<script async class="speakerdeck-embed" data-id="ec8f752883384847998cba94bb3dd746" data-ratio="1.7777777777777777" src="//speakerdeck.com/assets/embed.js"></script>

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

## Lernen

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

https://github.com/makenowjust/lernen

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

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

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

```rb
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 記法で出力されます。
出力された図を見てみます。

```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
```

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

<details><summary>to_mermaid の出力結果</summary>

```
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
```

</details>

:::

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

## 互換性の検証

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

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

```ruby
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` でも許容されるようになっています。

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

```rb
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
```

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

```mermaid
flowchart TD
  0(("0"))
  1((("1")))

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

```mermaid
flowchart TD
  0(("0"))
  1((("1")))
  3((("3")))

  0 -- "#quot;a#quot;" --> 1
  1 -- "#quot;b#quot;" --> 3
  3 -- "#quot;a#quot;" --> 1
```

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

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

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

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

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

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

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

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

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

```mermaid
flowchart TD
  0(("0"))
  1((("1")))
  3((("3")))

  0 -- "#quot;a#quot;" --> 1
  1 -- "#quot;b#quot;" --> 3
  3 -- "#quot;a#quot;" --> 1
```

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

## おわりに

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