2
$\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
$\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$
  • $\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 '17 at 18:01
  • $\begingroup$ It's only a problem if you are not allowed to use $\varepsilon$. $\endgroup$ – Yuval Filmus Mar 20 '17 at 18:02
  • $\begingroup$ Yes im allow to use it, sorry for not updating. and thanks. $\endgroup$ – limitless Mar 20 '17 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, privacy policy and cookie policy

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