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,*,+, ...)

  • $\begingroup$ Your title does not match your question. Please clarify. $\endgroup$ Aug 3, 2021 at 8:47

1 Answer 1


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$

Hence, a Turing machine that accepts exactly these expressions only need to simulate a pushdown automaton that accepts the language of the grammar, which is essentially just checking whether there is a closing ) for each ( and there are never more ) than ( in each prefix, which is a standard exercise in each course or textbook on formal languages.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.