2006/09/23

A is regular ==> A^R is regular

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

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

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

<< 回到主頁