字串反轉（string reversal）

反轉一個字串就是把它倒著寫，正像從右往左讀一個字。cat 的反轉是 tac，stressed 的反轉是 desserts。你保留所有相同的符號，只是翻轉它們的順序，讓最後一個變第一個、第一個變最後一個。

我們把字串 w 的反轉寫成 w^R。它的定義可逐符號給出：若 w = a1 a2 ... an，則 w^R = an ... a2 a1。空字串是它自己的反轉，ε^R = ε，單一符號也是它自己的反轉。反轉與串接的互動很俐落，但有個轉折：「先接再反轉」等於「先各自反轉再以相反順序接」，即 (xy)^R = y^R x^R，正如先穿襪再穿鞋的反向是先脫鞋再脫襪。反轉兩次會還原：(w^R)^R = w。

每當方向重要時反轉就會出現。回文恰好是等於自身反轉的字串（w = w^R），像 racecar。正規語言這一類在反轉下封閉，意思是若某有限自動機能識別一個語言，則某個有限自動機也能識別其反轉語言；這個事實是練習證明與「封閉性」主題的好材料。所以反轉既是一個簡單運算，也是探查機器能力的工具。