Mixing
Construct a regular expression
The problem asks me to construct a regular expression for the set of strings in {a,b}* that have even number of a and b.
What I have tried is (aa)* + (bb)* + (aabb)* but I believe it does not cover a string like abbbaaba.
Many thanks,
discrete-mathematics regular-expressions
asked Nov 20 '18 at 1:04
Alan Bui
163
|
show 1 more comment
The problem asks me to construct a regular expression for the set of strings in {a,b}* that have even number of a and b.
What I have tried is (aa)* + (bb)* + (aabb)* but I believe it does not cover a string like abbbaaba.
Many thanks,
discrete-mathematics regular-expressions
asked Nov 20 '18 at 1:04
Alan Bui
163
Where the $*$ in the post refers to a Kleene star for a finite alphabet: $A^* =cup_{n=1}^infty A^n$ ?
– Mason
Nov 20 '18 at 1:14
Can you be more simple please, I am quite new to this :)
– Alan Bui
Nov 20 '18 at 1:17
I have done anything yet. You use a $*$ in your post. What does it mean? It must mean kleene star?
– Mason
Nov 20 '18 at 1:19
@Mason yes it is
– Alan Bui
Nov 20 '18 at 1:21
3
Are you familiar with the procedure, given a deterministic finite state machine, to find a corresponding regular expression? If so, that's probably the approach I'd take - first, construct the state machine with states $EE,EO,OE,OO$ and then find the corresponding regular expression.
– Daniel Schepler
Nov 20 '18 at 1:22
|
show 1 more comment
The problem asks me to construct a regular expression for the set of strings in {a,b}* that have even number of a and b.
What I have tried is (aa)* + (bb)* + (aabb)* but I believe it does not cover a string like abbbaaba.
Many thanks,
discrete-mathematics regular-expressions
asked Nov 20 '18 at 1:04
Alan Bui
163
The problem asks me to construct a regular expression for the set of strings in {a,b}* that have even number of a and b.
What I have tried is (aa)* + (bb)* + (aabb)* but I believe it does not cover a string like abbbaaba.
Many thanks,
discrete-mathematics regular-expressions
discrete-mathematics regular-expressions
asked Nov 20 '18 at 1:04
Alan Bui
163
asked Nov 20 '18 at 1:04
Alan Bui
163
asked Nov 20 '18 at 1:04
Alan Bui
163
asked Nov 20 '18 at 1:04
Alan Bui
163
asked Nov 20 '18 at 1:04
Alan Bui
163
163
Where the $*$ in the post refers to a Kleene star for a finite alphabet: $A^* =cup_{n=1}^infty A^n$ ?
– Mason
Nov 20 '18 at 1:14
Can you be more simple please, I am quite new to this :)
– Alan Bui
Nov 20 '18 at 1:17
I have done anything yet. You use a $*$ in your post. What does it mean? It must mean kleene star?
– Mason
Nov 20 '18 at 1:19
@Mason yes it is
– Alan Bui
Nov 20 '18 at 1:21
3
Are you familiar with the procedure, given a deterministic finite state machine, to find a corresponding regular expression? If so, that's probably the approach I'd take - first, construct the state machine with states $EE,EO,OE,OO$ and then find the corresponding regular expression.
– Daniel Schepler
Nov 20 '18 at 1:22
|
show 1 more comment
Where the $*$ in the post refers to a Kleene star for a finite alphabet: $A^* =cup_{n=1}^infty A^n$ ?
– Mason
Nov 20 '18 at 1:14
Can you be more simple please, I am quite new to this :)
– Alan Bui
Nov 20 '18 at 1:17
I have done anything yet. You use a $*$ in your post. What does it mean? It must mean kleene star?
– Mason
Nov 20 '18 at 1:19
@Mason yes it is
– Alan Bui
Nov 20 '18 at 1:21
3
Are you familiar with the procedure, given a deterministic finite state machine, to find a corresponding regular expression? If so, that's probably the approach I'd take - first, construct the state machine with states $EE,EO,OE,OO$ and then find the corresponding regular expression.
– Daniel Schepler
Nov 20 '18 at 1:22
Where the $*$ in the post refers to a Kleene star for a finite alphabet: $A^* =cup_{n=1}^infty A^n$ ?
– Mason
Nov 20 '18 at 1:14
Where the $*$ in the post refers to a Kleene star for a finite alphabet: $A^* =cup_{n=1}^infty A^n$ ?
– Mason
Nov 20 '18 at 1:14
Can you be more simple please, I am quite new to this :)
– Alan Bui
Nov 20 '18 at 1:17
Can you be more simple please, I am quite new to this :)
– Alan Bui
Nov 20 '18 at 1:17
I have done anything yet. You use a $*$ in your post. What does it mean? It must mean kleene star?
– Mason
Nov 20 '18 at 1:19
I have done anything yet. You use a $*$ in your post. What does it mean? It must mean kleene star?
– Mason
Nov 20 '18 at 1:19
@Mason yes it is
– Alan Bui
Nov 20 '18 at 1:21
@Mason yes it is
– Alan Bui
Nov 20 '18 at 1:21
3
3
Are you familiar with the procedure, given a deterministic finite state machine, to find a corresponding regular expression? If so, that's probably the approach I'd take - first, construct the state machine with states $EE,EO,OE,OO$ and then find the corresponding regular expression.
– Daniel Schepler
Nov 20 '18 at 1:22
Are you familiar with the procedure, given a deterministic finite state machine, to find a corresponding regular expression? If so, that's probably the approach I'd take - first, construct the state machine with states $EE,EO,OE,OO$ and then find the corresponding regular expression.
– Daniel Schepler
Nov 20 '18 at 1:22
|
show 1 more comment
1 Answer
1
active
oldest
votes
If you have access to a complement operator $-$, we can implement Daniel Schepler's suggestion:
$$-(-(b^* ab^* ab^*)^* + -(a^* ba^* ba^*)^*).$$
Each interior parentheses says to look for two $a$'s which are separated by (any number of) $b$'s or vice versa. By putting the stars around these you allow yourself as many pairs as you want. The minus signs can be eliminated using De Morgan's Laws if you have access to an AND operator.
answered yesterday
aleph_two
22412
According to Wikipedia, it's possible to take any "generalized" regular expression and turn it into a regular expression presumably by some straightforward algorithm, but I'm not seeing how to it now.
– aleph_two
yesterday
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
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%2f3005788%2fconstruct-a-regular-expression%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
If you have access to a complement operator $-$, we can implement Daniel Schepler's suggestion:
$$-(-(b^* ab^* ab^*)^* + -(a^* ba^* ba^*)^*).$$
Each interior parentheses says to look for two $a$'s which are separated by (any number of) $b$'s or vice versa. By putting the stars around these you allow yourself as many pairs as you want. The minus signs can be eliminated using De Morgan's Laws if you have access to an AND operator.
answered yesterday
aleph_two
22412
According to Wikipedia, it's possible to take any "generalized" regular expression and turn it into a regular expression presumably by some straightforward algorithm, but I'm not seeing how to it now.
– aleph_two
yesterday
add a comment |
If you have access to a complement operator $-$, we can implement Daniel Schepler's suggestion:
$$-(-(b^* ab^* ab^*)^* + -(a^* ba^* ba^*)^*).$$
Each interior parentheses says to look for two $a$'s which are separated by (any number of) $b$'s or vice versa. By putting the stars around these you allow yourself as many pairs as you want. The minus signs can be eliminated using De Morgan's Laws if you have access to an AND operator.
answered yesterday
aleph_two
22412
According to Wikipedia, it's possible to take any "generalized" regular expression and turn it into a regular expression presumably by some straightforward algorithm, but I'm not seeing how to it now.
– aleph_two
yesterday
add a comment |
If you have access to a complement operator $-$, we can implement Daniel Schepler's suggestion:
$$-(-(b^* ab^* ab^*)^* + -(a^* ba^* ba^*)^*).$$
Each interior parentheses says to look for two $a$'s which are separated by (any number of) $b$'s or vice versa. By putting the stars around these you allow yourself as many pairs as you want. The minus signs can be eliminated using De Morgan's Laws if you have access to an AND operator.
answered yesterday
aleph_two
22412
If you have access to a complement operator $-$, we can implement Daniel Schepler's suggestion:
$$-(-(b^* ab^* ab^*)^* + -(a^* ba^* ba^*)^*).$$
Each interior parentheses says to look for two $a$'s which are separated by (any number of) $b$'s or vice versa. By putting the stars around these you allow yourself as many pairs as you want. The minus signs can be eliminated using De Morgan's Laws if you have access to an AND operator.
answered yesterday
aleph_two
22412
answered yesterday
aleph_two
22412
answered yesterday
aleph_two
22412
answered yesterday
aleph_two
22412
22412
According to Wikipedia, it's possible to take any "generalized" regular expression and turn it into a regular expression presumably by some straightforward algorithm, but I'm not seeing how to it now.
– aleph_two
yesterday
add a comment |
According to Wikipedia, it's possible to take any "generalized" regular expression and turn it into a regular expression presumably by some straightforward algorithm, but I'm not seeing how to it now.
– aleph_two
yesterday
According to Wikipedia, it's possible to take any "generalized" regular expression and turn it into a regular expression presumably by some straightforward algorithm, but I'm not seeing how to it now.
– aleph_two
yesterday
According to Wikipedia, it's possible to take any "generalized" regular expression and turn it into a regular expression presumably by some straightforward algorithm, but I'm not seeing how to it now.
– aleph_two
yesterday
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3005788%2fconstruct-a-regular-expression%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
Where the $*$ in the post refers to a Kleene star for a finite alphabet: $A^* =cup_{n=1}^infty A^n$ ?
– Mason
Nov 20 '18 at 1:14
Can you be more simple please, I am quite new to this :)
– Alan Bui
Nov 20 '18 at 1:17
I have done anything yet. You use a $*$ in your post. What does it mean? It must mean kleene star?
– Mason
Nov 20 '18 at 1:19
@Mason yes it is
– Alan Bui
Nov 20 '18 at 1:21
3
Are you familiar with the procedure, given a deterministic finite state machine, to find a corresponding regular expression? If so, that's probably the approach I'd take - first, construct the state machine with states $EE,EO,OE,OO$ and then find the corresponding regular expression.
– Daniel Schepler
Nov 20 '18 at 1:22