0
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Do you know the syntax and semantics of regular expressions? They’re described in the Wikipedia page on regular expressions. $\endgroup$ Commented Dec 27, 2020 at 20:02
  • $\begingroup$ 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? $\endgroup$
    – Bee
    Commented Dec 27, 2020 at 20:22
  • $\begingroup$ Right, this interpretation is correct. $\endgroup$ Commented Dec 27, 2020 at 20:24
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Jan 6, 2021 at 17:48
  • $\begingroup$ @D.W. again. this is not copy-pasted from another site. It is in fact a coursework question from my university. $\endgroup$
    – Bee
    Commented Jan 7, 2021 at 20:00

2 Answers 2

0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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*)+ ? $\endgroup$
    – Bee
    Commented Dec 27, 2020 at 21:40
  • $\begingroup$ yes, but $(b^*)^+$ does not make much sense to me, what are you trying to do for $b$? $\endgroup$
    – NimaJan
    Commented Dec 27, 2020 at 22:05
  • $\begingroup$ 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’? $\endgroup$
    – Bee
    Commented Dec 27, 2020 at 22:33
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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