Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Regular Expressions with at least 2 0's and at most 1

, ,
Problem Detail:

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.

#### Answered By : J.-E. Pin

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.