Mixing
Find a regular expression for binary strings to have odd non-empty blocks of 1s
$begingroup$
Write down a Regular Expression for the language $L$ consisting of all binary strings where every non-empty block of $1$s has odd length. (Notice that the empty string is in this language.)
My working out:
$$(111)^* 011$$
This way, there will always be an odd number of $1$s.
regular-language regular-expressions
edited Mar 28 '17 at 6:13
Fabio Somenzi
6,52821321
asked Mar 28 '17 at 2:21
MaggieMaggie
238
$endgroup$
add a comment |
$begingroup$
Write down a Regular Expression for the language $L$ consisting of all binary strings where every non-empty block of $1$s has odd length. (Notice that the empty string is in this language.)
My working out:
$$(111)^* 011$$
This way, there will always be an odd number of $1$s.
regular-language regular-expressions
edited Mar 28 '17 at 6:13
Fabio Somenzi
6,52821321
asked Mar 28 '17 at 2:21
MaggieMaggie
238
$endgroup$
$begingroup$
This doesn't seem to match the empty string.
$endgroup$
– John Hughes
Mar 28 '17 at 2:25
$begingroup$
How would you match an empty string?
$endgroup$
– Maggie
Mar 28 '17 at 2:36
$begingroup$
Well...the pattern [1]* matches it, because it matches "1" taken $0$ or more times.
$endgroup$
– John Hughes
Mar 28 '17 at 2:39
$begingroup$
You might want to draw an FSA that achieves what you want; from that, deriving the regular expression can be done mechanically.
$endgroup$
– John Hughes
Mar 28 '17 at 2:40
$begingroup$
Maybe I'm rusty on my regular expressions, but this doesn't look right. For one, you can generate an expression with an odd number of ones (111111011) or (011). For another, the question seems to be asking for every block of 1's (set of ones walled in by zero) should have odd length. So if you generate (111011) this would still be wrong, because even though the whole string has an odd number of ones, the last block of ones is not odd in length.
$endgroup$
– Tyberius
Mar 28 '17 at 3:49
add a comment |
$begingroup$
Write down a Regular Expression for the language $L$ consisting of all binary strings where every non-empty block of $1$s has odd length. (Notice that the empty string is in this language.)
My working out:
$$(111)^* 011$$
This way, there will always be an odd number of $1$s.
regular-language regular-expressions
edited Mar 28 '17 at 6:13
Fabio Somenzi
6,52821321
asked Mar 28 '17 at 2:21
MaggieMaggie
238
$endgroup$
Write down a Regular Expression for the language $L$ consisting of all binary strings where every non-empty block of $1$s has odd length. (Notice that the empty string is in this language.)
My working out:
$$(111)^* 011$$
This way, there will always be an odd number of $1$s.
regular-language regular-expressions
regular-language regular-expressions
edited Mar 28 '17 at 6:13
Fabio Somenzi
6,52821321
asked Mar 28 '17 at 2:21
MaggieMaggie
238
edited Mar 28 '17 at 6:13
Fabio Somenzi
6,52821321
asked Mar 28 '17 at 2:21
MaggieMaggie
238
edited Mar 28 '17 at 6:13
Fabio Somenzi
6,52821321
edited Mar 28 '17 at 6:13
Fabio Somenzi
6,52821321
edited Mar 28 '17 at 6:13
Fabio Somenzi
6,52821321
6,52821321
asked Mar 28 '17 at 2:21
MaggieMaggie
238
asked Mar 28 '17 at 2:21
MaggieMaggie
238
asked Mar 28 '17 at 2:21
MaggieMaggie
238
238
$begingroup$
This doesn't seem to match the empty string.
$endgroup$
– John Hughes
Mar 28 '17 at 2:25
$begingroup$
How would you match an empty string?
$endgroup$
– Maggie
Mar 28 '17 at 2:36
$begingroup$
Well...the pattern [1]* matches it, because it matches "1" taken $0$ or more times.
$endgroup$
– John Hughes
Mar 28 '17 at 2:39
$begingroup$
You might want to draw an FSA that achieves what you want; from that, deriving the regular expression can be done mechanically.
$endgroup$
– John Hughes
Mar 28 '17 at 2:40
$begingroup$
Maybe I'm rusty on my regular expressions, but this doesn't look right. For one, you can generate an expression with an odd number of ones (111111011) or (011). For another, the question seems to be asking for every block of 1's (set of ones walled in by zero) should have odd length. So if you generate (111011) this would still be wrong, because even though the whole string has an odd number of ones, the last block of ones is not odd in length.
$endgroup$
– Tyberius
Mar 28 '17 at 3:49
add a comment |
$begingroup$
This doesn't seem to match the empty string.
$endgroup$
– John Hughes
Mar 28 '17 at 2:25
$begingroup$
How would you match an empty string?
$endgroup$
– Maggie
Mar 28 '17 at 2:36
$begingroup$
Well...the pattern [1]* matches it, because it matches "1" taken $0$ or more times.
$endgroup$
– John Hughes
Mar 28 '17 at 2:39
$begingroup$
You might want to draw an FSA that achieves what you want; from that, deriving the regular expression can be done mechanically.
$endgroup$
– John Hughes
Mar 28 '17 at 2:40
$begingroup$
Maybe I'm rusty on my regular expressions, but this doesn't look right. For one, you can generate an expression with an odd number of ones (111111011) or (011). For another, the question seems to be asking for every block of 1's (set of ones walled in by zero) should have odd length. So if you generate (111011) this would still be wrong, because even though the whole string has an odd number of ones, the last block of ones is not odd in length.
$endgroup$
– Tyberius
Mar 28 '17 at 3:49
$begingroup$
This doesn't seem to match the empty string.
$endgroup$
– John Hughes
Mar 28 '17 at 2:25
$begingroup$
This doesn't seem to match the empty string.
$endgroup$
– John Hughes
Mar 28 '17 at 2:25
$begingroup$
How would you match an empty string?
$endgroup$
– Maggie
Mar 28 '17 at 2:36
$begingroup$
How would you match an empty string?
$endgroup$
– Maggie
Mar 28 '17 at 2:36
$begingroup$
Well...the pattern [1]* matches it, because it matches "1" taken $0$ or more times.
$endgroup$
– John Hughes
Mar 28 '17 at 2:39
$begingroup$
Well...the pattern [1]* matches it, because it matches "1" taken $0$ or more times.
$endgroup$
– John Hughes
Mar 28 '17 at 2:39
$begingroup$
You might want to draw an FSA that achieves what you want; from that, deriving the regular expression can be done mechanically.
$endgroup$
– John Hughes
Mar 28 '17 at 2:40
$begingroup$
You might want to draw an FSA that achieves what you want; from that, deriving the regular expression can be done mechanically.
$endgroup$
– John Hughes
Mar 28 '17 at 2:40
$begingroup$
Maybe I'm rusty on my regular expressions, but this doesn't look right. For one, you can generate an expression with an odd number of ones (111111011) or (011). For another, the question seems to be asking for every block of 1's (set of ones walled in by zero) should have odd length. So if you generate (111011) this would still be wrong, because even though the whole string has an odd number of ones, the last block of ones is not odd in length.
$endgroup$
– Tyberius
Mar 28 '17 at 3:49
$begingroup$
Maybe I'm rusty on my regular expressions, but this doesn't look right. For one, you can generate an expression with an odd number of ones (111111011) or (011). For another, the question seems to be asking for every block of 1's (set of ones walled in by zero) should have odd length. So if you generate (111011) this would still be wrong, because even though the whole string has an odd number of ones, the last block of ones is not odd in length.
$endgroup$
– Tyberius
Mar 28 '17 at 3:49
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Let's look at your regular expression:
$$ (111)^* 011 enspace. $$
It generates the strings $011$, $111011$, $111111011$, and so on. None of these words is such that every nonempty block of $1$s has odd length. Moreover, the total number of $1$s alternates between even and odd, contrary to your claim. Even if we had guaranteed blocks of $1$s of odd lengths, as in
$$ 1(11)^*01(11)^* enspace, $$
our goal is not to describe some of the words in $L$, but all of them. This is not entirely trivial in this case; therefore let's take another, more systematic approach.
The strings in our language may start with any number of $0$s. So, we are going to use $0^*$ as a building block. A nonempty string of $1$s of odd length is given by $1(11)^*$. That's another building block for our regular expression. From $1(11)^*$ we get $1$, $111$, $11111$, and so on.
Finally, in between blocks of $1$s we can have any positive number of $0$s. That is, $00^*$. Let's now put these building blocks together:
$$ 0^* (1(11)^* 00^*)^* (1(11)^* + epsilon) enspace. $$
It's not the simplest regular expression out there, but we should be able to recognize the building blocks. We start with an optional block of $0$s. Then we have zero or more blocks of $1$s of odd lengths, each followed by one or more zeros. Finally, we have an optional block of $1$s (of odd length) not followed by $0$s to account for the fact that a word in $L$ may not have trailing $0$s.
This is not the only regular expression for $L$, as is often the case. If you have already seen Kleene's Theorem, you should know of the systematic procedure alluded to by John Hughes in his comment. For this $L$ it produces a regular expression of complexity comparable to the one above.
answered Mar 28 '17 at 5:20
Fabio SomenziFabio Somenzi
6,52821321
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2206298%2ffind-a-regular-expression-for-binary-strings-to-have-odd-non-empty-blocks-of-1s%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let's look at your regular expression:
$$ (111)^* 011 enspace. $$
It generates the strings $011$, $111011$, $111111011$, and so on. None of these words is such that every nonempty block of $1$s has odd length. Moreover, the total number of $1$s alternates between even and odd, contrary to your claim. Even if we had guaranteed blocks of $1$s of odd lengths, as in
$$ 1(11)^*01(11)^* enspace, $$
our goal is not to describe some of the words in $L$, but all of them. This is not entirely trivial in this case; therefore let's take another, more systematic approach.
The strings in our language may start with any number of $0$s. So, we are going to use $0^*$ as a building block. A nonempty string of $1$s of odd length is given by $1(11)^*$. That's another building block for our regular expression. From $1(11)^*$ we get $1$, $111$, $11111$, and so on.
Finally, in between blocks of $1$s we can have any positive number of $0$s. That is, $00^*$. Let's now put these building blocks together:
$$ 0^* (1(11)^* 00^*)^* (1(11)^* + epsilon) enspace. $$
It's not the simplest regular expression out there, but we should be able to recognize the building blocks. We start with an optional block of $0$s. Then we have zero or more blocks of $1$s of odd lengths, each followed by one or more zeros. Finally, we have an optional block of $1$s (of odd length) not followed by $0$s to account for the fact that a word in $L$ may not have trailing $0$s.
This is not the only regular expression for $L$, as is often the case. If you have already seen Kleene's Theorem, you should know of the systematic procedure alluded to by John Hughes in his comment. For this $L$ it produces a regular expression of complexity comparable to the one above.
answered Mar 28 '17 at 5:20
Fabio SomenziFabio Somenzi
6,52821321
$endgroup$
add a comment |
$begingroup$
Let's look at your regular expression:
$$ (111)^* 011 enspace. $$
It generates the strings $011$, $111011$, $111111011$, and so on. None of these words is such that every nonempty block of $1$s has odd length. Moreover, the total number of $1$s alternates between even and odd, contrary to your claim. Even if we had guaranteed blocks of $1$s of odd lengths, as in
$$ 1(11)^*01(11)^* enspace, $$
our goal is not to describe some of the words in $L$, but all of them. This is not entirely trivial in this case; therefore let's take another, more systematic approach.
The strings in our language may start with any number of $0$s. So, we are going to use $0^*$ as a building block. A nonempty string of $1$s of odd length is given by $1(11)^*$. That's another building block for our regular expression. From $1(11)^*$ we get $1$, $111$, $11111$, and so on.
Finally, in between blocks of $1$s we can have any positive number of $0$s. That is, $00^*$. Let's now put these building blocks together:
$$ 0^* (1(11)^* 00^*)^* (1(11)^* + epsilon) enspace. $$
It's not the simplest regular expression out there, but we should be able to recognize the building blocks. We start with an optional block of $0$s. Then we have zero or more blocks of $1$s of odd lengths, each followed by one or more zeros. Finally, we have an optional block of $1$s (of odd length) not followed by $0$s to account for the fact that a word in $L$ may not have trailing $0$s.
This is not the only regular expression for $L$, as is often the case. If you have already seen Kleene's Theorem, you should know of the systematic procedure alluded to by John Hughes in his comment. For this $L$ it produces a regular expression of complexity comparable to the one above.
answered Mar 28 '17 at 5:20
Fabio SomenziFabio Somenzi
6,52821321
$endgroup$
add a comment |
$begingroup$
Let's look at your regular expression:
$$ (111)^* 011 enspace. $$
It generates the strings $011$, $111011$, $111111011$, and so on. None of these words is such that every nonempty block of $1$s has odd length. Moreover, the total number of $1$s alternates between even and odd, contrary to your claim. Even if we had guaranteed blocks of $1$s of odd lengths, as in
$$ 1(11)^*01(11)^* enspace, $$
our goal is not to describe some of the words in $L$, but all of them. This is not entirely trivial in this case; therefore let's take another, more systematic approach.
The strings in our language may start with any number of $0$s. So, we are going to use $0^*$ as a building block. A nonempty string of $1$s of odd length is given by $1(11)^*$. That's another building block for our regular expression. From $1(11)^*$ we get $1$, $111$, $11111$, and so on.
Finally, in between blocks of $1$s we can have any positive number of $0$s. That is, $00^*$. Let's now put these building blocks together:
$$ 0^* (1(11)^* 00^*)^* (1(11)^* + epsilon) enspace. $$
It's not the simplest regular expression out there, but we should be able to recognize the building blocks. We start with an optional block of $0$s. Then we have zero or more blocks of $1$s of odd lengths, each followed by one or more zeros. Finally, we have an optional block of $1$s (of odd length) not followed by $0$s to account for the fact that a word in $L$ may not have trailing $0$s.
This is not the only regular expression for $L$, as is often the case. If you have already seen Kleene's Theorem, you should know of the systematic procedure alluded to by John Hughes in his comment. For this $L$ it produces a regular expression of complexity comparable to the one above.
answered Mar 28 '17 at 5:20
Fabio SomenziFabio Somenzi
6,52821321
$endgroup$
Let's look at your regular expression:
$$ (111)^* 011 enspace. $$
It generates the strings $011$, $111011$, $111111011$, and so on. None of these words is such that every nonempty block of $1$s has odd length. Moreover, the total number of $1$s alternates between even and odd, contrary to your claim. Even if we had guaranteed blocks of $1$s of odd lengths, as in
$$ 1(11)^*01(11)^* enspace, $$
our goal is not to describe some of the words in $L$, but all of them. This is not entirely trivial in this case; therefore let's take another, more systematic approach.
The strings in our language may start with any number of $0$s. So, we are going to use $0^*$ as a building block. A nonempty string of $1$s of odd length is given by $1(11)^*$. That's another building block for our regular expression. From $1(11)^*$ we get $1$, $111$, $11111$, and so on.
Finally, in between blocks of $1$s we can have any positive number of $0$s. That is, $00^*$. Let's now put these building blocks together:
$$ 0^* (1(11)^* 00^*)^* (1(11)^* + epsilon) enspace. $$
It's not the simplest regular expression out there, but we should be able to recognize the building blocks. We start with an optional block of $0$s. Then we have zero or more blocks of $1$s of odd lengths, each followed by one or more zeros. Finally, we have an optional block of $1$s (of odd length) not followed by $0$s to account for the fact that a word in $L$ may not have trailing $0$s.
This is not the only regular expression for $L$, as is often the case. If you have already seen Kleene's Theorem, you should know of the systematic procedure alluded to by John Hughes in his comment. For this $L$ it produces a regular expression of complexity comparable to the one above.
answered Mar 28 '17 at 5:20
Fabio SomenziFabio Somenzi
6,52821321
answered Mar 28 '17 at 5:20
Fabio SomenziFabio Somenzi
6,52821321
answered Mar 28 '17 at 5:20
Fabio SomenziFabio Somenzi
6,52821321
answered Mar 28 '17 at 5:20
Fabio SomenziFabio Somenzi
6,52821321
6,52821321
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2206298%2ffind-a-regular-expression-for-binary-strings-to-have-odd-non-empty-blocks-of-1s%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
This doesn't seem to match the empty string.
$endgroup$
– John Hughes
Mar 28 '17 at 2:25
$begingroup$
How would you match an empty string?
$endgroup$
– Maggie
Mar 28 '17 at 2:36
$begingroup$
Well...the pattern [1]* matches it, because it matches "1" taken $0$ or more times.
$endgroup$
– John Hughes
Mar 28 '17 at 2:39
$begingroup$
You might want to draw an FSA that achieves what you want; from that, deriving the regular expression can be done mechanically.
$endgroup$
– John Hughes
Mar 28 '17 at 2:40
$begingroup$
Maybe I'm rusty on my regular expressions, but this doesn't look right. For one, you can generate an expression with an odd number of ones (111111011) or (011). For another, the question seems to be asking for every block of 1's (set of ones walled in by zero) should have odd length. So if you generate (111011) this would still be wrong, because even though the whole string has an odd number of ones, the last block of ones is not odd in length.
$endgroup$
– Tyberius
Mar 28 '17 at 3:49