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

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.

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.
• 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 ? – limitless Mar 20 '17 at 18:01
• It's only a problem if you are not allowed to use $\varepsilon$. – Yuval Filmus Mar 20 '17 at 18:02
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$$