Cheap and Secure Web Hosting Provider : See Now

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

, , No Comments
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.

Asked By : tom

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41326

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback