patternMinor
Regular expression generating the language $L=\{w: |w|\le 5\}$
Viewed 0 times
expressiontheregularlanguagegenerating
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#71803, answer score: 2
Revisions (0)
No revisions yet.