3
$\begingroup$

Im trying to find a regular expression to generate the language that has words with length at most 5, over $\Sigma =\{0,1\}$ How can i represent the at most ? I know i can do it if ill just write all the $2^5$ possibilties with 'or' between them. But it seem to me not the right way. Is it even possible to represent the state : "I've choose 0, 1, or nothing" ?

I can use only the elemntary operators : $\cup , \cdot , ^*$

Also it was easyer to find a NFA that will represent L but the algorithem to get the regex from the aotomton will give me the exponential answer.

$\endgroup$

2 Answers 2

2
$\begingroup$

If you are allowed to use $\epsilon$, then you can represent "0, 1, or nothing" using $0+1+\epsilon$, and using this it is easy to come up with a short regular expression.

If you are not allowed to use $\epsilon$, then you can use the fact that $L = \bigcup_{i=0}^5 \{ w : |w|=i \}$ to come up with a fairly short regular expression, though I don't know how you would match the empty string.

$\endgroup$
3
  • $\begingroup$ why would the empty string be a problem ? If ill pick in every state $\varepsilon$ ill get $\varepsilon \cdot \varepsilon \cdot \varepsilon \cdot \varepsilon \cdot \varepsilon $ which is $\varepsilon$ isnt it ? $\endgroup$
    – limitless
    Mar 20, 2017 at 18:01
  • $\begingroup$ It's only a problem if you are not allowed to use $\varepsilon$. $\endgroup$ Mar 20, 2017 at 18:02
  • $\begingroup$ Yes im allow to use it, sorry for not updating. and thanks. $\endgroup$
    – limitless
    Mar 20, 2017 at 18:02
2
$\begingroup$

Yes, for "0,1 or nothing", you can write it as $$(\Sigma | \epsilon)$$ where $\Sigma$ is your alphabet.

So, for strings of length at most $5$, the expression would be $$(\Sigma | \epsilon)^5$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.