\pojem{Regulární výrazy} $RV(\Sigma)$ nad konečnou neprázdnou abecedou $\Sigma=\{x_1,x_2,\ldots,x_n\}$ a jejich hodnota $L(\alpha)$ jsou definovány induktivně: Základ: \begin{enumerate} \item Konstanty $\lambda$ a $\emptyset$ jsou regulární výrazy s hodnotami $L(\lambda)=\{\lambda\}$ a $L(\emptyset)=\emptyset$ (někdy značeno $\left[\lambda\right]$, $\left[\emptyset\right]$). \item Je--li $a\in \Sigma$, je ${\bf a}$ regulární výraz s hodnotou $L({\bf a})=\{a\}$. \item řecká písmena z počátku abecedy $\alpha,\beta$ budeme používat jako proměnné reprezentující libovolný jazyk $\alpha\in RV(\Sigma)$. \end{enumerate}
Indukce: Jsou--li $\alpha$ a $\beta$ regulární výrazy s hodnotami $L(\alpha)$ and $L(\beta)$, pak \begin{enumerate} \item $\alpha+\beta$ je RE s hodnotou $L(\alpha+\beta)=L(\alpha)\cup L(\beta) $. \item $\alpha\beta$ je RE s hodnotou $L(\alpha\beta)=L(\alpha)L(\beta)$. (Tečce používané u řetězců se vyhýbáme, aby se nepletla s jiným významem v UNIX grep příkazu.) \item uzávěr $\alpha^*$ je RE s hodnotou $L(\alpha^*)=(L(\alpha))^*$. \item $(\alpha)$ je RE se stejnou hodnotou jako $\alpha$, i.e. $L((\alpha))=L(\alpha)$. \end{enumerate} Každý regulární výraz dostaneme indukcí výše, tj. třída $RE(\Sigma)$ je nejmenší třída uzavřená na uvedené operace.