1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Apr 13 '15 at 12:27
  • $\begingroup$ You gave your guess at the answer, but not the question. $\;$ $\endgroup$ – user12859 Apr 14 '15 at 2:14
2
$\begingroup$

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.

$\endgroup$

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.