# How do you read the regular expression (0^∗10^+)^+?

Give an example of a string in the language of $$(0^*10^+)^+$$.

I've been asked to give an example of a string in this language but I'm confused on how to read this notation. I'm guessing the acceptable strings are supposed to start with 0, but that's about all I can infer.

• Do you know the syntax and semantics of regular expressions? They’re described in the Wikipedia page on regular expressions. Commented Dec 27, 2020 at 20:02
• Yes I went through my textbook which I found quite confusing, but after reading the wiki page I think its a little clearer now. Correct me if I’m wrong, but this is my interpretation of the regex: strings must start with 0, zero or more times followed by a 1, then a 0 one or more times. Everything in the brackets can appear one or more times in a string. E.g. 01000100?
– Bee
Commented Dec 27, 2020 at 20:22
• Right, this interpretation is correct. Commented Dec 27, 2020 at 20:24
• This appears to be copied from somewhere (e.g., chegg.com/homework-help/questions-and-answers/…, chegg.com/homework-help/questions-and-answers/…, math.stackexchange.com/q/3965830/14578). We require you to credit the source of all copied material: cs.stackexchange.com/help/referencing.
– D.W.
Commented Jan 6, 2021 at 17:48
• @D.W. again. this is not copy-pasted from another site. It is in fact a coursework question from my university.
– Bee
Commented Jan 7, 2021 at 20:00

As I see in the comments, I think you have a bit of confusion in the syntax and semantics of regular expressions.

• $$^*$$ stands for Kleene star, which means "zero or more repetitions". (the string can be empty)
• $$+$$ stands for Kleene plus, which means "one or more repetitions". (the string cannot be empty)

So for your example $$(0^∗10^+)^+$$ you should first look inside the brackets:

1. $$0^*$$ can be empty or $$0$$,$$00$$,$$000$$,$$\dots$$
2. $$10^+$$ can't be empty, so it only can be of the form $$10,1010,101010,10101010,\dots$$

So now we can combine them and we can take for example $$001010$$. But this is still around brackets and has the form kleene plus ($$+$$), so this can be $$(001010)^+=001010,001010001010,001010001010001010,\dots$$

So we can take the string $$001010001010$$ as an example for this regular expression.

• so if I was to design a regular expression that accepts the language of all binary strings with exactly one occurrence of aa, would it be written like: aa(b*)+ ?
– Bee
Commented Dec 27, 2020 at 21:40
• yes, but $(b^*)^+$ does not make much sense to me, what are you trying to do for $b$? Commented Dec 27, 2020 at 22:05
• I see what the error is now. The expression was supposed to mean: any string that begins with aa and occurs only once, after which b occurs zero or more times, and everything in the brackets occurs one or more times. If b occurs zero times, but the star outside the bracket makes it occur at least one time, I guess this makes it conflicting right? Let me write another expression: b*aab+ Does this satisfy my previous statement ‘design a regular expression that accepts the language of all binary strings with exactly one occurrence of aa’?
– Bee
Commented Dec 27, 2020 at 22:33

This regular expression describes the language of all words over $$\{0,1\}$$ which do not consist entirely of $$0$$-s, and in which every $$1$$ is followed by $$0$$.