各 n について n 文字の受理語の数が等しい2つの正規言語が与えられたとき、なんと文字から文字への関数型トランスデューサーを用いて、なんと2つの正規言語の間の全単射を作ることができる。有限状態のみで一方の言語から他方の言語へ逐次変換できるのである。
https://t.co/peNtj1Gi8e https://t.co/ioUAIlYD5s
普通のオートマトンの状態遷移は、0/1 の値に and の積と or の和を入れた半環の行列として表現できる。これを拡張し、一般の半環で考えるのが重み付きオートマトンである。各状態にいる/いないではなくどれだけの「重み」でいるかが遷移していく。例は重みが自然数の場合。
https://t.co/peNtj1Gi8e https://t.co/i1TbfDa0Dy
各 n についてオートマトンの受理する n 文字の語の数を返す数え上げ関数の母関数が有理式になる話。隣接行列 E を n 乗することで n 文字先の状態遷移の数え上げが表現でき、冪乗の和 I+zE+(zE)^2+… が十分小さい z に対し逆行列 (I-zE)^-1 になることから求まる。
https://t.co/peNtj1Gi8e https://t.co/70AjUNqk1N