Regular expression generating the language $L=\{w: |w|\le 5\}$

Question

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.

Answer 1

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.

Answer 2

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$$