0

Given $\Sigma = \{ 0,1,2 \}$, write a regular expression for $$\{ w \in \Sigma^* : w \text{ does not contain the substring 110} \}\;.$$

I know how to do a regular expression for a language that does not contain a substring of two consequent characters, but here it is three and I've been trying alot. Any direction would help!

Brian M. Scott
  • 616,228
TheNotMe
  • 4,841
  • It’s $\Sigma$ that’s ${0,1,2}$, not $\Sigma^*$. What regular expression would you write for the language over $\Sigma$ of words that don’t contain the substring $10$? – Brian M. Scott Oct 29 '13 at 09:45
  • Sorry,edited. Trying to think of such a regular expression. – TheNotMe Oct 29 '13 at 09:54

1 Answers1

0

A possible solution is

$\bigl((\epsilon + 1 + 11)(0 + 2)\bigr)^*(\epsilon + 1 + 11)$

See this answer for more details on how this expression was obtained.

J.-E. Pin
  • 40,163