A is regular ==> A^R is regular

從昨天睡前開始想這題，到剛剛完成證明。題目和證明都在 external link。昨晚原本很直覺地想用「建造一部 DFA（or NFA）」的方式證明，但想不出什麼好法子，只好先睡覺。今早想到從 regular expression 下手，但因為邏輯上沒有已知工具可用而寫不出證明，幸好自己大約想到一個推廣的數學歸納法，並從 Wikipedia 得到其學名 "structural induction"，而得以順利完成論證。證明完後都會覺得很簡單 XD。

現在到處看都會隱隱浮現（抽象）代數結構，讓人有點按捺不住。數圖閱讀就先找本代數來看吧。

--
有沒有人能用造機器的方式證明呢？