# Regular Expressions with at least 2 0's and at most 1

I think the answer should be:

$(1+ \epsilon)000^* + 0^*0(1+\epsilon)00^* + 000^*(1+\epsilon)$

But I am not sure if this is the right answer. Can someone explain the correct answer? And if it is correct how can I shorten this up?

Also what is the nfa for the regular expression: ∅*

i have one more problem: i can't surely understand the meaning of Σ* symbol. As far as I understand it should be (0+1)* if Σ = (0, 1) and (a+b+c)* if Σ = (a,b,c) and so on. Please someone clarify this.

• Looks fine to me: either there's no 1, or there's a 1 with two 0s before it, or after it, or one before and one after. I doubt there's a significantly shorter way of writing it. – David Richerby Apr 13 '15 at 12:27
• You gave your guess at the answer, but not the question. $\;$ – user12859 Apr 14 '15 at 2:14

## 1 Answer

Your answer is correct. You can obtain a slightly shorter expression by deleting two of the $\epsilon$ in your expression. Indeed \begin{align} (1+ \epsilon)000^* + 0^*0(1+\epsilon)00^* + 000^*(1+\epsilon) &= (1+ \epsilon)000^* + 0^*0100^* + 000^*1 \\ &= 1000^* + 0^*0(1+\epsilon)00^* + 000^*1\\ &=1000^* + 0^*0100^* + 000^*(1+\epsilon) \end{align} Finally, if you want to avoid $\epsilon$, you could use one of the expressions $$000^* + 1000^* + 0^*0100^* + 000^*1 \quad \text{or} \quad 0^*(00 + 100 + 010 + 001)0^*$$ which might be easier to read.