makenowjust-labs/blog

Automata Learning とは、未知の (ブラックボックス) システムに対する入力とその出力から、システムの振舞いを有限状態オートマトンとして再現する手法です。 これは、仕様が形式化されていないシステムに対して形式的な手法を適用するための足掛りになるなど、近年重要な技術となっています。

Angluin による$L\ast$は Automata Learning のアルゴリズムの中でも最も代表的な存在です。 $L\ast$は未知の正規言語を教師を使って学習するアルゴリズムで、多くの Automata Learning の基礎となっています。

この記事では$L\ast$の、その原理やアルゴリズムの詳細について解説します。

前々から課題として感じていた、このブログの OGP 画像の自動生成を実装しました。 OGP 画像は Twitter などの SNS にシェアするときに表示される画像です。

この記事では自動生成の実装や、skia-canvas や budoux といったライブラリを利用して、タイトルの自動改行や高速な生成を実現したので、それらについても解説します。

JavaScript のソースコードを小さくする方法として UglifyJS や Terser といった minification ツールを用いるものが良く知られています。 これらはソースコード中の空白やコメントを削除し、変数名などを短い形式にすることで、ソースコードを小さくしています。

こういった minification ツールを適用し、さらに GZip などで圧縮して配信するのが今日の Web での標準的な方法となっています。 ですが、JavaScript を圧縮できる可能性のある方法として、自己解凍的な圧縮技術を用いる、というアイディアがあります。

この記事では、そういった自己解凍的な圧縮技術として JS Crush や Roadroller について紹介します。

元々は GatsbyJS で作られていたこのブログを、Next.js で書き直して復活させました。 放置している間にもいくつか記事にしたい事柄があったのですが、元の仕組みでは記事を書く気が起きず、結果的に 1 年近く放置することになってしまいました。

この記事では「なぜ GatsbyJS から移行したのか」と「他のフレームワークを比較した結果」、そして「最終的な技術スタック」について説明します。

前回の記事では DFA 最小化アルゴリズムとして Brzozowski のアルゴリズムを解説しました。 今回は、別の最小化アルゴリズムとして Hopcroft のアルゴリズムについて解説します。

"Introduction to Automata Theory, Languages, and Computation" (日本語訳『オートマトン 言語理論 計算論』) の著者の一人として知られる John Hopcroft が 1971 年に発表したアルゴリズムです。 実装を工夫することで最悪計算量は DFA の状態数 $n$ に対して $O(n \log n)$ となることが知られています。 しかし、正当さがやや直感的でないことから、オートマトン理論の教科書や講義などで触れられる機会は少ないように思います。

この記事では、Hopcroft のアルゴリズムの実装に加えて、その正しさの証明や計算量の解析を行います。