Proof for equivalence of two regular expressions
up vote
2
down vote
favorite
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 at 15:31
alex4ero
183
add a comment |
up vote
2
down vote
favorite
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 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 at 15:49
Sorry, but I can't read it. You ought to type it.
– saulspatz
Nov 21 at 15:51
Looks good now.
– Jean-Claude Arbaut
Nov 21 at 16:07
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
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 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 at 15:31
alex4ero
183
asked Nov 21 at 15:31
alex4ero
183
edited Nov 21 at 16:05
asked Nov 21 at 15:31
alex4ero
183
asked Nov 21 at 15:31
alex4ero
183
asked Nov 21 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 at 15:49
Sorry, but I can't read it. You ought to type it.
– saulspatz
Nov 21 at 15:51
Looks good now.
– Jean-Claude Arbaut
Nov 21 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 at 15:49
Sorry, but I can't read it. You ought to type it.
– saulspatz
Nov 21 at 15:51
Looks good now.
– Jean-Claude Arbaut
Nov 21 at 16:07
I added a picture of my best try so far. This is also, where I'm stuck.
– alex4ero
Nov 21 at 15:49
I added a picture of my best try so far. This is also, where I'm stuck.
– alex4ero
Nov 21 at 15:49
Sorry, but I can't read it. You ought to type it.
– saulspatz
Nov 21 at 15:51
Sorry, but I can't read it. You ought to type it.
– saulspatz
Nov 21 at 15:51
Looks good now.
– Jean-Claude Arbaut
Nov 21 at 16:07
Looks good now.
– Jean-Claude Arbaut
Nov 21 at 16:07
add a comment |
2 Answers
2
active
oldest
votes
up vote
1
down vote
accepted
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 at 16:20
Jean-Claude Arbaut
14.7k63363
Wow, this is a very fast and beautiful solution. Thank you very much!
– alex4ero
Nov 21 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 at 15:51
@Federico See the first line. Admittedly not the shortest way.
– Jean-Claude Arbaut
Nov 29 at 17:23
Oh, well, yeah... Sorry I didn't see it :D
– Federico
Nov 29 at 17:37
add a comment |
up vote
2
down vote
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 at 16:15
Federico
4,184512
How do you prove the fact that you are using?
– J.-E. Pin
Nov 29 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 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 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 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 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
up vote
1
down vote
accepted
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 at 16:20
Jean-Claude Arbaut
14.7k63363
Wow, this is a very fast and beautiful solution. Thank you very much!
– alex4ero
Nov 21 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 at 15:51
@Federico See the first line. Admittedly not the shortest way.
– Jean-Claude Arbaut
Nov 29 at 17:23
Oh, well, yeah... Sorry I didn't see it :D
– Federico
Nov 29 at 17:37
add a comment |
up vote
1
down vote
accepted
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 at 16:20
Jean-Claude Arbaut
14.7k63363
Wow, this is a very fast and beautiful solution. Thank you very much!
– alex4ero
Nov 21 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 at 15:51
@Federico See the first line. Admittedly not the shortest way.
– Jean-Claude Arbaut
Nov 29 at 17:23
Oh, well, yeah... Sorry I didn't see it :D
– Federico
Nov 29 at 17:37
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
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 at 16:20
Jean-Claude Arbaut
14.7k63363
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 at 16:20
Jean-Claude Arbaut
14.7k63363
edited Nov 21 at 17:26
answered Nov 21 at 16:20
Jean-Claude Arbaut
14.7k63363
answered Nov 21 at 16:20
Jean-Claude Arbaut
14.7k63363
answered Nov 21 at 16:20
Jean-Claude Arbaut
14.7k63363
14.7k63363
Wow, this is a very fast and beautiful solution. Thank you very much!
– alex4ero
Nov 21 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 at 15:51
@Federico See the first line. Admittedly not the shortest way.
– Jean-Claude Arbaut
Nov 29 at 17:23
Oh, well, yeah... Sorry I didn't see it :D
– Federico
Nov 29 at 17:37
add a comment |
Wow, this is a very fast and beautiful solution. Thank you very much!
– alex4ero
Nov 21 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 at 15:51
@Federico See the first line. Admittedly not the shortest way.
– Jean-Claude Arbaut
Nov 29 at 17:23
Oh, well, yeah... Sorry I didn't see it :D
– Federico
Nov 29 at 17:37
Wow, this is a very fast and beautiful solution. Thank you very much!
– alex4ero
Nov 21 at 16:40
Wow, this is a very fast and beautiful solution. Thank you very much!
– alex4ero
Nov 21 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 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 at 15:51
@Federico See the first line. Admittedly not the shortest way.
– Jean-Claude Arbaut
Nov 29 at 17:23
@Federico See the first line. Admittedly not the shortest way.
– Jean-Claude Arbaut
Nov 29 at 17:23
Oh, well, yeah... Sorry I didn't see it :D
– Federico
Nov 29 at 17:37
Oh, well, yeah... Sorry I didn't see it :D
– Federico
Nov 29 at 17:37
add a comment |
up vote
2
down vote
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 at 16:15
Federico
4,184512
How do you prove the fact that you are using?
– J.-E. Pin
Nov 29 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 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 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 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 at 15:21
|
show 1 more comment
up vote
2
down vote
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 at 16:15
Federico
4,184512
How do you prove the fact that you are using?
– J.-E. Pin
Nov 29 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 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 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 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 at 15:21
|
show 1 more comment
up vote
2
down vote
up vote
2
down vote
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 at 16:15
Federico
4,184512
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 at 16:15
Federico
4,184512
edited Nov 29 at 16:01
answered Nov 21 at 16:15
Federico
4,184512
answered Nov 21 at 16:15
Federico
4,184512
answered Nov 21 at 16:15
Federico
4,184512
4,184512
How do you prove the fact that you are using?
– J.-E. Pin
Nov 29 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 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 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 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 at 15:21
|
show 1 more comment
How do you prove the fact that you are using?
– J.-E. Pin
Nov 29 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 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 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 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 at 15:21
How do you prove the fact that you are using?
– J.-E. Pin
Nov 29 at 8:19
How do you prove the fact that you are using?
– J.-E. Pin
Nov 29 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 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 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 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 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 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 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 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 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 at 15:49
Sorry, but I can't read it. You ought to type it.
– saulspatz
Nov 21 at 15:51
Looks good now.
– Jean-Claude Arbaut
Nov 21 at 16:07