Mixing
Proof for equivalence of two regular expressions
I have to show via equivalence transformation, that these two regular expressions are equivalent:
$$(ab+b^*a^*) = (a+b^*)(a^*+b)$$
Can someone give me a hint how to show this? I am only allowed to use these equivalences:
$$
R+S = S+R \
(R+S)+T = R+(S+T) \
(R S) T = R (S T) \
emptyset + R = R + emptyset = R \
varepsilon R = R varepsilon = R \
emptyset R = R emptyset = emptyset \
R (S + T) = RS + RT \
(S + T)R = SR + TR \
R + R = R\
(R^*)^* = R^* \
(varepsilon + R)^* = R^* \
emptyset^* = varepsilon \
varepsilon^* = varepsilon \
(varepsilon + R)R^* = R^*(varepsilon + R) = R^*\
RR^* = R^*R \
R^* + R = R^* \
varepsilon + RR^* = R^*
$$
My best attempt so far.
formal-languages regular-expressions
asked Nov 21 '18 at 15:31
alex4ero
183
add a comment |
I have to show via equivalence transformation, that these two regular expressions are equivalent:
$$(ab+b^*a^*) = (a+b^*)(a^*+b)$$
Can someone give me a hint how to show this? I am only allowed to use these equivalences:
$$
R+S = S+R \
(R+S)+T = R+(S+T) \
(R S) T = R (S T) \
emptyset + R = R + emptyset = R \
varepsilon R = R varepsilon = R \
emptyset R = R emptyset = emptyset \
R (S + T) = RS + RT \
(S + T)R = SR + TR \
R + R = R\
(R^*)^* = R^* \
(varepsilon + R)^* = R^* \
emptyset^* = varepsilon \
varepsilon^* = varepsilon \
(varepsilon + R)R^* = R^*(varepsilon + R) = R^*\
RR^* = R^*R \
R^* + R = R^* \
varepsilon + RR^* = R^*
$$
My best attempt so far.
formal-languages regular-expressions
asked Nov 21 '18 at 15:31
alex4ero
183
I added a picture of my best try so far. This is also, where I'm stuck.
– alex4ero
Nov 21 '18 at 15:49
Sorry, but I can't read it. You ought to type it.
– saulspatz
Nov 21 '18 at 15:51
Looks good now.
– Jean-Claude Arbaut
Nov 21 '18 at 16:07
add a comment |
I have to show via equivalence transformation, that these two regular expressions are equivalent:
$$(ab+b^*a^*) = (a+b^*)(a^*+b)$$
Can someone give me a hint how to show this? I am only allowed to use these equivalences:
$$
R+S = S+R \
(R+S)+T = R+(S+T) \
(R S) T = R (S T) \
emptyset + R = R + emptyset = R \
varepsilon R = R varepsilon = R \
emptyset R = R emptyset = emptyset \
R (S + T) = RS + RT \
(S + T)R = SR + TR \
R + R = R\
(R^*)^* = R^* \
(varepsilon + R)^* = R^* \
emptyset^* = varepsilon \
varepsilon^* = varepsilon \
(varepsilon + R)R^* = R^*(varepsilon + R) = R^*\
RR^* = R^*R \
R^* + R = R^* \
varepsilon + RR^* = R^*
$$
My best attempt so far.
formal-languages regular-expressions
asked Nov 21 '18 at 15:31
alex4ero
183
I have to show via equivalence transformation, that these two regular expressions are equivalent:
$$(ab+b^*a^*) = (a+b^*)(a^*+b)$$
Can someone give me a hint how to show this? I am only allowed to use these equivalences:
$$
R+S = S+R \
(R+S)+T = R+(S+T) \
(R S) T = R (S T) \
emptyset + R = R + emptyset = R \
varepsilon R = R varepsilon = R \
emptyset R = R emptyset = emptyset \
R (S + T) = RS + RT \
(S + T)R = SR + TR \
R + R = R\
(R^*)^* = R^* \
(varepsilon + R)^* = R^* \
emptyset^* = varepsilon \
varepsilon^* = varepsilon \
(varepsilon + R)R^* = R^*(varepsilon + R) = R^*\
RR^* = R^*R \
R^* + R = R^* \
varepsilon + RR^* = R^*
$$
My best attempt so far.
formal-languages regular-expressions
formal-languages regular-expressions
asked Nov 21 '18 at 15:31
alex4ero
183
asked Nov 21 '18 at 15:31
alex4ero
183
edited Nov 21 '18 at 16:05
asked Nov 21 '18 at 15:31
alex4ero
183
asked Nov 21 '18 at 15:31
alex4ero
183
asked Nov 21 '18 at 15:31
alex4ero
183
183
I added a picture of my best try so far. This is also, where I'm stuck.
– alex4ero
Nov 21 '18 at 15:49
Sorry, but I can't read it. You ought to type it.
– saulspatz
Nov 21 '18 at 15:51
Looks good now.
– Jean-Claude Arbaut
Nov 21 '18 at 16:07
add a comment |
I added a picture of my best try so far. This is also, where I'm stuck.
– alex4ero
Nov 21 '18 at 15:49
Sorry, but I can't read it. You ought to type it.
– saulspatz
Nov 21 '18 at 15:51
Looks good now.
– Jean-Claude Arbaut
Nov 21 '18 at 16:07
I added a picture of my best try so far. This is also, where I'm stuck.
– alex4ero
Nov 21 '18 at 15:49
I added a picture of my best try so far. This is also, where I'm stuck.
– alex4ero
Nov 21 '18 at 15:49
Sorry, but I can't read it. You ought to type it.
– saulspatz
Nov 21 '18 at 15:51
Sorry, but I can't read it. You ought to type it.
– saulspatz
Nov 21 '18 at 15:51
Looks good now.
– Jean-Claude Arbaut
Nov 21 '18 at 16:07
Looks good now.
– Jean-Claude Arbaut
Nov 21 '18 at 16:07
add a comment |
2 Answers
2
active
oldest
votes
First, for any $R$,
$$R^*+epsilon=epsilon+(epsilon+R)R^*=epsilon+epsilon R^*+RR^*=epsilon+R^*+RR^*=R^*+(epsilon+RR^*)=R^*+R^*=R^*$$
So
$$b^*a^*=(b^*+epsilon)a^*=b^*a^*+epsilon a^*=b^*a^*+a^*=b^*a^*+(epsilon+a)a^*=b^*a^*+epsilon a^*+aa^*=(b^*+epsilon)a^*+aa^*=b^*a^*+aa^*$$
Likewise
$$b^*a^*=b^*(a^*+epsilon)=b^*a^*+b^*epsilon=b^*a^*+b^*=b^*a^*+(epsilon+b)b^*=b^*a^*+epsilon b^*+bb^*\=b^*a^*+b^*epsilon+b^*b=b^*(a^*+epsilon)+b^*b=b^*a^*+b^*b$$
So that $b^*a^*=b^*a^*+aa^*+b^*b$.
Now
$$(a+b^*)(a^*+b)=(a+b^*)a^*+(a+b^*)b=aa^*+b^*a^*+ab+b^*b=ab+b^*a^*$$
answered Nov 21 '18 at 16:20
Jean-Claude Arbaut
14.7k63464
Wow, this is a very fast and beautiful solution. Thank you very much!
– alex4ero
Nov 21 '18 at 16:40
At the beginning of the second equation, you are using $b^*=b^*+epsilon$. Since this is not among the given equivalences, you should probably provide a derivation. A possible one is as follows: $R^*+epsilon=RR^*+epsilon+epsilon = RR^*+epsilon=R^*$.
– Federico
Nov 29 '18 at 15:51
@Federico See the first line. Admittedly not the shortest way.
– Jean-Claude Arbaut
Nov 29 '18 at 17:23
Oh, well, yeah... Sorry I didn't see it :D
– Federico
Nov 29 '18 at 17:37
add a comment |
EDIT to clarify my answer. The core of the solution is highlighted in yellow.
I introduce the following useful concept, that permits to better reason about regular expressions.
Definition. I write $Rsubset S$ if there exists $T$ such that $R+T=S$.
Lemma. If $Rsubset S$, then $R+S=S$.
Proof. $R+S = R + (R+T) = (R+R)+T = R+T=S$. □
Now, back to your problem. We have
$$
(a+b^*)(b+a^*)
= ab + aa^* + b^*b + b^*a^* ,
$$
but $aa^*subset b^*a^*$ and $b^*bsubset b^*a^*$, so
$$
(a+b^*)(b+a^*)
= ab + b^*a^* .
$$
You may ask, why is $aa^*subset b^*a^*?$ Well, that's easy 'cause
$$
b^*a^* = (epsilon+b^*)(epsilon+a)a^* = aa^* + text{other terms}.
$$
For the nitpickers.
In the last formula, we used also $b^*=b^*+epsilon$ at the beginning. Since this is not among the given equivalences, a possible derivation is as follows: $R^*+epsilon=RR^*+epsilon+epsilon = RR^*+epsilon=R^*$.
Otherwise, using our useful subset concept, notice that $epsilonsubset R^*$, because $R^*=epsilon+RR^*$; but then our lemma says $R^*+epsilon=R^*$.
To conclude, I urge you to try the same exercise with a more complicate regular expression and see whether this subset thing does indeed simplify the derivations or not.
Just compare my short formulas with those of the accepted answer.
answered Nov 21 '18 at 16:15
Federico
4,799514
How do you prove the fact that you are using?
– J.-E. Pin
Nov 29 '18 at 8:19
Well, $Rsubset S$ means that $S=R+T$ for some $T$, but then in particular $R+S=R+R+T=R+T=S$
– Federico
Nov 29 '18 at 12:47
I mean, it's quite obvious if you think that $R$ is the set of matched strings and $+$ is the set union: $Rsubset S implies Rcup S=S$
– Federico
Nov 29 '18 at 12:48
The question is how to use the equivalences given in the question and I am afraid your answer does not give any proof.
– J.-E. Pin
Nov 29 '18 at 13:09
You might then ask why $aa^*subset b^*a^*$, but that is also clear, as $b^*a^* = (b^*+epsilon)(a+epsilon)a^*=(b^*+epsilon)(aa^*+a^*)=aa^*+mathrm{others}$
– Federico
Nov 29 '18 at 15:21
|
show 1 more 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%2f3007872%2fproof-for-equivalence-of-two-regular-expressions%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
First, for any $R$,
$$R^*+epsilon=epsilon+(epsilon+R)R^*=epsilon+epsilon R^*+RR^*=epsilon+R^*+RR^*=R^*+(epsilon+RR^*)=R^*+R^*=R^*$$
So
$$b^*a^*=(b^*+epsilon)a^*=b^*a^*+epsilon a^*=b^*a^*+a^*=b^*a^*+(epsilon+a)a^*=b^*a^*+epsilon a^*+aa^*=(b^*+epsilon)a^*+aa^*=b^*a^*+aa^*$$
Likewise
$$b^*a^*=b^*(a^*+epsilon)=b^*a^*+b^*epsilon=b^*a^*+b^*=b^*a^*+(epsilon+b)b^*=b^*a^*+epsilon b^*+bb^*\=b^*a^*+b^*epsilon+b^*b=b^*(a^*+epsilon)+b^*b=b^*a^*+b^*b$$
So that $b^*a^*=b^*a^*+aa^*+b^*b$.
Now
$$(a+b^*)(a^*+b)=(a+b^*)a^*+(a+b^*)b=aa^*+b^*a^*+ab+b^*b=ab+b^*a^*$$
answered Nov 21 '18 at 16:20
Jean-Claude Arbaut
14.7k63464
Wow, this is a very fast and beautiful solution. Thank you very much!
– alex4ero
Nov 21 '18 at 16:40
At the beginning of the second equation, you are using $b^*=b^*+epsilon$. Since this is not among the given equivalences, you should probably provide a derivation. A possible one is as follows: $R^*+epsilon=RR^*+epsilon+epsilon = RR^*+epsilon=R^*$.
– Federico
Nov 29 '18 at 15:51
@Federico See the first line. Admittedly not the shortest way.
– Jean-Claude Arbaut
Nov 29 '18 at 17:23
Oh, well, yeah... Sorry I didn't see it :D
– Federico
Nov 29 '18 at 17:37
add a comment |
First, for any $R$,
$$R^*+epsilon=epsilon+(epsilon+R)R^*=epsilon+epsilon R^*+RR^*=epsilon+R^*+RR^*=R^*+(epsilon+RR^*)=R^*+R^*=R^*$$
So
$$b^*a^*=(b^*+epsilon)a^*=b^*a^*+epsilon a^*=b^*a^*+a^*=b^*a^*+(epsilon+a)a^*=b^*a^*+epsilon a^*+aa^*=(b^*+epsilon)a^*+aa^*=b^*a^*+aa^*$$
Likewise
$$b^*a^*=b^*(a^*+epsilon)=b^*a^*+b^*epsilon=b^*a^*+b^*=b^*a^*+(epsilon+b)b^*=b^*a^*+epsilon b^*+bb^*\=b^*a^*+b^*epsilon+b^*b=b^*(a^*+epsilon)+b^*b=b^*a^*+b^*b$$
So that $b^*a^*=b^*a^*+aa^*+b^*b$.
Now
$$(a+b^*)(a^*+b)=(a+b^*)a^*+(a+b^*)b=aa^*+b^*a^*+ab+b^*b=ab+b^*a^*$$
answered Nov 21 '18 at 16:20
Jean-Claude Arbaut
14.7k63464
Wow, this is a very fast and beautiful solution. Thank you very much!
– alex4ero
Nov 21 '18 at 16:40
At the beginning of the second equation, you are using $b^*=b^*+epsilon$. Since this is not among the given equivalences, you should probably provide a derivation. A possible one is as follows: $R^*+epsilon=RR^*+epsilon+epsilon = RR^*+epsilon=R^*$.
– Federico
Nov 29 '18 at 15:51
@Federico See the first line. Admittedly not the shortest way.
– Jean-Claude Arbaut
Nov 29 '18 at 17:23
Oh, well, yeah... Sorry I didn't see it :D
– Federico
Nov 29 '18 at 17:37
add a comment |
First, for any $R$,
$$R^*+epsilon=epsilon+(epsilon+R)R^*=epsilon+epsilon R^*+RR^*=epsilon+R^*+RR^*=R^*+(epsilon+RR^*)=R^*+R^*=R^*$$
So
$$b^*a^*=(b^*+epsilon)a^*=b^*a^*+epsilon a^*=b^*a^*+a^*=b^*a^*+(epsilon+a)a^*=b^*a^*+epsilon a^*+aa^*=(b^*+epsilon)a^*+aa^*=b^*a^*+aa^*$$
Likewise
$$b^*a^*=b^*(a^*+epsilon)=b^*a^*+b^*epsilon=b^*a^*+b^*=b^*a^*+(epsilon+b)b^*=b^*a^*+epsilon b^*+bb^*\=b^*a^*+b^*epsilon+b^*b=b^*(a^*+epsilon)+b^*b=b^*a^*+b^*b$$
So that $b^*a^*=b^*a^*+aa^*+b^*b$.
Now
$$(a+b^*)(a^*+b)=(a+b^*)a^*+(a+b^*)b=aa^*+b^*a^*+ab+b^*b=ab+b^*a^*$$
answered Nov 21 '18 at 16:20
Jean-Claude Arbaut
14.7k63464
First, for any $R$,
$$R^*+epsilon=epsilon+(epsilon+R)R^*=epsilon+epsilon R^*+RR^*=epsilon+R^*+RR^*=R^*+(epsilon+RR^*)=R^*+R^*=R^*$$
So
$$b^*a^*=(b^*+epsilon)a^*=b^*a^*+epsilon a^*=b^*a^*+a^*=b^*a^*+(epsilon+a)a^*=b^*a^*+epsilon a^*+aa^*=(b^*+epsilon)a^*+aa^*=b^*a^*+aa^*$$
Likewise
$$b^*a^*=b^*(a^*+epsilon)=b^*a^*+b^*epsilon=b^*a^*+b^*=b^*a^*+(epsilon+b)b^*=b^*a^*+epsilon b^*+bb^*\=b^*a^*+b^*epsilon+b^*b=b^*(a^*+epsilon)+b^*b=b^*a^*+b^*b$$
So that $b^*a^*=b^*a^*+aa^*+b^*b$.
Now
$$(a+b^*)(a^*+b)=(a+b^*)a^*+(a+b^*)b=aa^*+b^*a^*+ab+b^*b=ab+b^*a^*$$
answered Nov 21 '18 at 16:20
Jean-Claude Arbaut
14.7k63464
edited Nov 21 '18 at 17:26
answered Nov 21 '18 at 16:20
Jean-Claude Arbaut
14.7k63464
answered Nov 21 '18 at 16:20
Jean-Claude Arbaut
14.7k63464
answered Nov 21 '18 at 16:20
Jean-Claude Arbaut
14.7k63464
14.7k63464
Wow, this is a very fast and beautiful solution. Thank you very much!
– alex4ero
Nov 21 '18 at 16:40
At the beginning of the second equation, you are using $b^*=b^*+epsilon$. Since this is not among the given equivalences, you should probably provide a derivation. A possible one is as follows: $R^*+epsilon=RR^*+epsilon+epsilon = RR^*+epsilon=R^*$.
– Federico
Nov 29 '18 at 15:51
@Federico See the first line. Admittedly not the shortest way.
– Jean-Claude Arbaut
Nov 29 '18 at 17:23
Oh, well, yeah... Sorry I didn't see it :D
– Federico
Nov 29 '18 at 17:37
add a comment |
Wow, this is a very fast and beautiful solution. Thank you very much!
– alex4ero
Nov 21 '18 at 16:40
At the beginning of the second equation, you are using $b^*=b^*+epsilon$. Since this is not among the given equivalences, you should probably provide a derivation. A possible one is as follows: $R^*+epsilon=RR^*+epsilon+epsilon = RR^*+epsilon=R^*$.
– Federico
Nov 29 '18 at 15:51
@Federico See the first line. Admittedly not the shortest way.
– Jean-Claude Arbaut
Nov 29 '18 at 17:23
Oh, well, yeah... Sorry I didn't see it :D
– Federico
Nov 29 '18 at 17:37
Wow, this is a very fast and beautiful solution. Thank you very much!
– alex4ero
Nov 21 '18 at 16:40
Wow, this is a very fast and beautiful solution. Thank you very much!
– alex4ero
Nov 21 '18 at 16:40
At the beginning of the second equation, you are using $b^*=b^*+epsilon$. Since this is not among the given equivalences, you should probably provide a derivation. A possible one is as follows: $R^*+epsilon=RR^*+epsilon+epsilon = RR^*+epsilon=R^*$.
– Federico
Nov 29 '18 at 15:51
At the beginning of the second equation, you are using $b^*=b^*+epsilon$. Since this is not among the given equivalences, you should probably provide a derivation. A possible one is as follows: $R^*+epsilon=RR^*+epsilon+epsilon = RR^*+epsilon=R^*$.
– Federico
Nov 29 '18 at 15:51
@Federico See the first line. Admittedly not the shortest way.
– Jean-Claude Arbaut
Nov 29 '18 at 17:23
@Federico See the first line. Admittedly not the shortest way.
– Jean-Claude Arbaut
Nov 29 '18 at 17:23
Oh, well, yeah... Sorry I didn't see it :D
– Federico
Nov 29 '18 at 17:37
Oh, well, yeah... Sorry I didn't see it :D
– Federico
Nov 29 '18 at 17:37
add a comment |
EDIT to clarify my answer. The core of the solution is highlighted in yellow.
I introduce the following useful concept, that permits to better reason about regular expressions.
Definition. I write $Rsubset S$ if there exists $T$ such that $R+T=S$.
Lemma. If $Rsubset S$, then $R+S=S$.
Proof. $R+S = R + (R+T) = (R+R)+T = R+T=S$. □
Now, back to your problem. We have
$$
(a+b^*)(b+a^*)
= ab + aa^* + b^*b + b^*a^* ,
$$
but $aa^*subset b^*a^*$ and $b^*bsubset b^*a^*$, so
$$
(a+b^*)(b+a^*)
= ab + b^*a^* .
$$
You may ask, why is $aa^*subset b^*a^*?$ Well, that's easy 'cause
$$
b^*a^* = (epsilon+b^*)(epsilon+a)a^* = aa^* + text{other terms}.
$$
For the nitpickers.
In the last formula, we used also $b^*=b^*+epsilon$ at the beginning. Since this is not among the given equivalences, a possible derivation is as follows: $R^*+epsilon=RR^*+epsilon+epsilon = RR^*+epsilon=R^*$.
Otherwise, using our useful subset concept, notice that $epsilonsubset R^*$, because $R^*=epsilon+RR^*$; but then our lemma says $R^*+epsilon=R^*$.
To conclude, I urge you to try the same exercise with a more complicate regular expression and see whether this subset thing does indeed simplify the derivations or not.
Just compare my short formulas with those of the accepted answer.
answered Nov 21 '18 at 16:15
Federico
4,799514
How do you prove the fact that you are using?
– J.-E. Pin
Nov 29 '18 at 8:19
Well, $Rsubset S$ means that $S=R+T$ for some $T$, but then in particular $R+S=R+R+T=R+T=S$
– Federico
Nov 29 '18 at 12:47
I mean, it's quite obvious if you think that $R$ is the set of matched strings and $+$ is the set union: $Rsubset S implies Rcup S=S$
– Federico
Nov 29 '18 at 12:48
The question is how to use the equivalences given in the question and I am afraid your answer does not give any proof.
– J.-E. Pin
Nov 29 '18 at 13:09
You might then ask why $aa^*subset b^*a^*$, but that is also clear, as $b^*a^* = (b^*+epsilon)(a+epsilon)a^*=(b^*+epsilon)(aa^*+a^*)=aa^*+mathrm{others}$
– Federico
Nov 29 '18 at 15:21
|
show 1 more comment
EDIT to clarify my answer. The core of the solution is highlighted in yellow.
I introduce the following useful concept, that permits to better reason about regular expressions.
Definition. I write $Rsubset S$ if there exists $T$ such that $R+T=S$.
Lemma. If $Rsubset S$, then $R+S=S$.
Proof. $R+S = R + (R+T) = (R+R)+T = R+T=S$. □
Now, back to your problem. We have
$$
(a+b^*)(b+a^*)
= ab + aa^* + b^*b + b^*a^* ,
$$
but $aa^*subset b^*a^*$ and $b^*bsubset b^*a^*$, so
$$
(a+b^*)(b+a^*)
= ab + b^*a^* .
$$
You may ask, why is $aa^*subset b^*a^*?$ Well, that's easy 'cause
$$
b^*a^* = (epsilon+b^*)(epsilon+a)a^* = aa^* + text{other terms}.
$$
For the nitpickers.
In the last formula, we used also $b^*=b^*+epsilon$ at the beginning. Since this is not among the given equivalences, a possible derivation is as follows: $R^*+epsilon=RR^*+epsilon+epsilon = RR^*+epsilon=R^*$.
Otherwise, using our useful subset concept, notice that $epsilonsubset R^*$, because $R^*=epsilon+RR^*$; but then our lemma says $R^*+epsilon=R^*$.
To conclude, I urge you to try the same exercise with a more complicate regular expression and see whether this subset thing does indeed simplify the derivations or not.
Just compare my short formulas with those of the accepted answer.
answered Nov 21 '18 at 16:15
Federico
4,799514
How do you prove the fact that you are using?
– J.-E. Pin
Nov 29 '18 at 8:19
Well, $Rsubset S$ means that $S=R+T$ for some $T$, but then in particular $R+S=R+R+T=R+T=S$
– Federico
Nov 29 '18 at 12:47
I mean, it's quite obvious if you think that $R$ is the set of matched strings and $+$ is the set union: $Rsubset S implies Rcup S=S$
– Federico
Nov 29 '18 at 12:48
The question is how to use the equivalences given in the question and I am afraid your answer does not give any proof.
– J.-E. Pin
Nov 29 '18 at 13:09
You might then ask why $aa^*subset b^*a^*$, but that is also clear, as $b^*a^* = (b^*+epsilon)(a+epsilon)a^*=(b^*+epsilon)(aa^*+a^*)=aa^*+mathrm{others}$
– Federico
Nov 29 '18 at 15:21
|
show 1 more comment
EDIT to clarify my answer. The core of the solution is highlighted in yellow.
I introduce the following useful concept, that permits to better reason about regular expressions.
Definition. I write $Rsubset S$ if there exists $T$ such that $R+T=S$.
Lemma. If $Rsubset S$, then $R+S=S$.
Proof. $R+S = R + (R+T) = (R+R)+T = R+T=S$. □
Now, back to your problem. We have
$$
(a+b^*)(b+a^*)
= ab + aa^* + b^*b + b^*a^* ,
$$
but $aa^*subset b^*a^*$ and $b^*bsubset b^*a^*$, so
$$
(a+b^*)(b+a^*)
= ab + b^*a^* .
$$
You may ask, why is $aa^*subset b^*a^*?$ Well, that's easy 'cause
$$
b^*a^* = (epsilon+b^*)(epsilon+a)a^* = aa^* + text{other terms}.
$$
For the nitpickers.
In the last formula, we used also $b^*=b^*+epsilon$ at the beginning. Since this is not among the given equivalences, a possible derivation is as follows: $R^*+epsilon=RR^*+epsilon+epsilon = RR^*+epsilon=R^*$.
Otherwise, using our useful subset concept, notice that $epsilonsubset R^*$, because $R^*=epsilon+RR^*$; but then our lemma says $R^*+epsilon=R^*$.
To conclude, I urge you to try the same exercise with a more complicate regular expression and see whether this subset thing does indeed simplify the derivations or not.
Just compare my short formulas with those of the accepted answer.
answered Nov 21 '18 at 16:15
Federico
4,799514
EDIT to clarify my answer. The core of the solution is highlighted in yellow.
I introduce the following useful concept, that permits to better reason about regular expressions.
Definition. I write $Rsubset S$ if there exists $T$ such that $R+T=S$.
Lemma. If $Rsubset S$, then $R+S=S$.
Proof. $R+S = R + (R+T) = (R+R)+T = R+T=S$. □
Now, back to your problem. We have
$$
(a+b^*)(b+a^*)
= ab + aa^* + b^*b + b^*a^* ,
$$
but $aa^*subset b^*a^*$ and $b^*bsubset b^*a^*$, so
$$
(a+b^*)(b+a^*)
= ab + b^*a^* .
$$
You may ask, why is $aa^*subset b^*a^*?$ Well, that's easy 'cause
$$
b^*a^* = (epsilon+b^*)(epsilon+a)a^* = aa^* + text{other terms}.
$$
For the nitpickers.
In the last formula, we used also $b^*=b^*+epsilon$ at the beginning. Since this is not among the given equivalences, a possible derivation is as follows: $R^*+epsilon=RR^*+epsilon+epsilon = RR^*+epsilon=R^*$.
Otherwise, using our useful subset concept, notice that $epsilonsubset R^*$, because $R^*=epsilon+RR^*$; but then our lemma says $R^*+epsilon=R^*$.
To conclude, I urge you to try the same exercise with a more complicate regular expression and see whether this subset thing does indeed simplify the derivations or not.
Just compare my short formulas with those of the accepted answer.
answered Nov 21 '18 at 16:15
Federico
4,799514
edited Nov 29 '18 at 16:01
answered Nov 21 '18 at 16:15
Federico
4,799514
answered Nov 21 '18 at 16:15
Federico
4,799514
answered Nov 21 '18 at 16:15
Federico
4,799514
4,799514
How do you prove the fact that you are using?
– J.-E. Pin
Nov 29 '18 at 8:19
Well, $Rsubset S$ means that $S=R+T$ for some $T$, but then in particular $R+S=R+R+T=R+T=S$
– Federico
Nov 29 '18 at 12:47
I mean, it's quite obvious if you think that $R$ is the set of matched strings and $+$ is the set union: $Rsubset S implies Rcup S=S$
– Federico
Nov 29 '18 at 12:48
The question is how to use the equivalences given in the question and I am afraid your answer does not give any proof.
– J.-E. Pin
Nov 29 '18 at 13:09
You might then ask why $aa^*subset b^*a^*$, but that is also clear, as $b^*a^* = (b^*+epsilon)(a+epsilon)a^*=(b^*+epsilon)(aa^*+a^*)=aa^*+mathrm{others}$
– Federico
Nov 29 '18 at 15:21
|
show 1 more comment
How do you prove the fact that you are using?
– J.-E. Pin
Nov 29 '18 at 8:19
Well, $Rsubset S$ means that $S=R+T$ for some $T$, but then in particular $R+S=R+R+T=R+T=S$
– Federico
Nov 29 '18 at 12:47
I mean, it's quite obvious if you think that $R$ is the set of matched strings and $+$ is the set union: $Rsubset S implies Rcup S=S$
– Federico
Nov 29 '18 at 12:48
The question is how to use the equivalences given in the question and I am afraid your answer does not give any proof.
– J.-E. Pin
Nov 29 '18 at 13:09
You might then ask why $aa^*subset b^*a^*$, but that is also clear, as $b^*a^* = (b^*+epsilon)(a+epsilon)a^*=(b^*+epsilon)(aa^*+a^*)=aa^*+mathrm{others}$
– Federico
Nov 29 '18 at 15:21
How do you prove the fact that you are using?
– J.-E. Pin
Nov 29 '18 at 8:19
How do you prove the fact that you are using?
– J.-E. Pin
Nov 29 '18 at 8:19
Well, $Rsubset S$ means that $S=R+T$ for some $T$, but then in particular $R+S=R+R+T=R+T=S$
– Federico
Nov 29 '18 at 12:47
Well, $Rsubset S$ means that $S=R+T$ for some $T$, but then in particular $R+S=R+R+T=R+T=S$
– Federico
Nov 29 '18 at 12:47
I mean, it's quite obvious if you think that $R$ is the set of matched strings and $+$ is the set union: $Rsubset S implies Rcup S=S$
– Federico
Nov 29 '18 at 12:48
I mean, it's quite obvious if you think that $R$ is the set of matched strings and $+$ is the set union: $Rsubset S implies Rcup S=S$
– Federico
Nov 29 '18 at 12:48
The question is how to use the equivalences given in the question and I am afraid your answer does not give any proof.
– J.-E. Pin
Nov 29 '18 at 13:09
The question is how to use the equivalences given in the question and I am afraid your answer does not give any proof.
– J.-E. Pin
Nov 29 '18 at 13:09
You might then ask why $aa^*subset b^*a^*$, but that is also clear, as $b^*a^* = (b^*+epsilon)(a+epsilon)a^*=(b^*+epsilon)(aa^*+a^*)=aa^*+mathrm{others}$
– Federico
Nov 29 '18 at 15:21
You might then ask why $aa^*subset b^*a^*$, but that is also clear, as $b^*a^* = (b^*+epsilon)(a+epsilon)a^*=(b^*+epsilon)(aa^*+a^*)=aa^*+mathrm{others}$
– Federico
Nov 29 '18 at 15:21
|
show 1 more 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%2f3007872%2fproof-for-equivalence-of-two-regular-expressions%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
I added a picture of my best try so far. This is also, where I'm stuck.
– alex4ero
Nov 21 '18 at 15:49
Sorry, but I can't read it. You ought to type it.
– saulspatz
Nov 21 '18 at 15:51
Looks good now.
– Jean-Claude Arbaut
Nov 21 '18 at 16:07