Si indica con $w^R$ la stringa reverse (o inversa) di $w$, cioè la stringa $w$ scritta “al contrario”: se $w = a_1 ... a_n$, allora $w^R = a_n... a_1$. Formalmente, il reverse $w^R$ di $w\in \Sigma^*$ è definito induttivamente nel modo seguente:
$$ w^R = \begin{cases} \epsilon &\text{se }w = \epsilon \\ ax^R &\text{se } w = xa, \ \text{con } x\in \Sigma^*\text{ e } a \in \Sigma \end{cases} $$
Il reverse di un linguaggio $L$, indicato con $L^R$, è il linguaggio
$$ L^R = \{w^R \ | \ w \in L\} $$
Utilizzando questa definizione induttiva di reverse di una stringa si dimostra che, se la stringa $w$ è composta da due stringhe $\alpha, \beta \in \Sigma^*$, cioè $w = \alpha\beta$, allora
$$ w^R = \beta^R \alpha ^R $$
La dimostrazione è per induzione su $|\beta|$.
Siano $L$ e $M$ due linguaggi qualunque (non necessariamente regolari). Valgono le seguenti proprietà:
Le dimostrazioni sono relativamente semplici, e non verranno presentate; sostanzialmente, la 1 segue da $(\alpha\beta)^R = \beta^R\alpha^R$, la 2 segue dalla 1 e la 3 segue dalla 2.
Data un’espressione regolare $E$, l’espressione reverse di $E$, indicata con $E^R$, è definita induttivamente sulla struttura di $E$:
$$ E^R = \begin{cases} E &\text{se } E=\empty, \ E=\epsilon\ o\ E=a\in \Sigma \\ S^R + T^R &\text{se } E= S + T \\ T^R \cdot S^R &\text{se } E = S\cdot T \\ (S^R)^* &\text{se } E = S^* \\ (S^R) &\text{se } E = (S) \end{cases} $$