# High Level description of Turing Machines

How can create a Turing machine that checks whether or not an input string is a well-defined regular expression? For example, it recognizes a language that consists of string over {0,1} and the symbols used to write down REs (U,*,+, ...)

Using a fixed alphabet $$\Sigma$$, one can define regular expressions over $$\Sigma$$ inductively:
• $$\varnothing$$ and each $$a \in \Sigma$$ are regular expressions.
• if $$r$$ and $$e$$ are regular expressions then so are $$(r + e)$$, $$(r \cdot e)$$, and $$r^\ast$$.
From there it is easy to define a context-free grammar for all regular expressions over $$\Sigma$$ with the following productions:
• $$S \to \varnothing \mid a$$ for all $$a \in \Sigma$$
• $$S \to (S + S) \mid (S \cdot S) \mid S^\ast$$