Mixing
'$L$ almost' is regular
up vote
1
down vote
favorite
Given a regular language $L$, I have to prove that '$L$ almost' is regular where '$L$ almost' is all the words which differ from the words of $L$ by one char.
for example, if $L = {aab,aaa}$, so $bab$ belongs to '$L$ almost' because it differs from $aab$ only by the first letter.
I have found this problem's solution and I simply can not understand the transition function.
If someone can explain it or maybe suggest a different one, that would be fantastic.
The most difficult part is the part of $t$,$t'$ so if you can be explicit when it comes to this part I would appreciate that.
Explanation of the picture (it's in Hebrew):
$L$ is regular so there is a DFA $M$ which defines it. They are creating an NFA based on the DFA by making two copies of the DFA, and moving from one to the other.
Any help understanding the transition function will do.
Thank a lot in advance!
Solution
computer-science formal-languages automata regular-language
edited yesterday
Joey Kilpatrick
1,070121
asked Nov 15 at 15:34
Avishai Yaniv
63
New contributor
Avishai Yaniv is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
1
down vote
favorite
Given a regular language $L$, I have to prove that '$L$ almost' is regular where '$L$ almost' is all the words which differ from the words of $L$ by one char.
for example, if $L = {aab,aaa}$, so $bab$ belongs to '$L$ almost' because it differs from $aab$ only by the first letter.
I have found this problem's solution and I simply can not understand the transition function.
If someone can explain it or maybe suggest a different one, that would be fantastic.
The most difficult part is the part of $t$,$t'$ so if you can be explicit when it comes to this part I would appreciate that.
Explanation of the picture (it's in Hebrew):
$L$ is regular so there is a DFA $M$ which defines it. They are creating an NFA based on the DFA by making two copies of the DFA, and moving from one to the other.
Any help understanding the transition function will do.
Thank a lot in advance!
Solution
computer-science formal-languages automata regular-language
edited yesterday
Joey Kilpatrick
1,070121
asked Nov 15 at 15:34
Avishai Yaniv
63
New contributor
Avishai Yaniv is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Given a regular language $L$, I have to prove that '$L$ almost' is regular where '$L$ almost' is all the words which differ from the words of $L$ by one char.
for example, if $L = {aab,aaa}$, so $bab$ belongs to '$L$ almost' because it differs from $aab$ only by the first letter.
I have found this problem's solution and I simply can not understand the transition function.
If someone can explain it or maybe suggest a different one, that would be fantastic.
The most difficult part is the part of $t$,$t'$ so if you can be explicit when it comes to this part I would appreciate that.
Explanation of the picture (it's in Hebrew):
$L$ is regular so there is a DFA $M$ which defines it. They are creating an NFA based on the DFA by making two copies of the DFA, and moving from one to the other.
Any help understanding the transition function will do.
Thank a lot in advance!
Solution
computer-science formal-languages automata regular-language
edited yesterday
Joey Kilpatrick
1,070121
asked Nov 15 at 15:34
Avishai Yaniv
63
New contributor
Avishai Yaniv is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Given a regular language $L$, I have to prove that '$L$ almost' is regular where '$L$ almost' is all the words which differ from the words of $L$ by one char.
for example, if $L = {aab,aaa}$, so $bab$ belongs to '$L$ almost' because it differs from $aab$ only by the first letter.
I have found this problem's solution and I simply can not understand the transition function.
If someone can explain it or maybe suggest a different one, that would be fantastic.
The most difficult part is the part of $t$,$t'$ so if you can be explicit when it comes to this part I would appreciate that.
Explanation of the picture (it's in Hebrew):
$L$ is regular so there is a DFA $M$ which defines it. They are creating an NFA based on the DFA by making two copies of the DFA, and moving from one to the other.
Any help understanding the transition function will do.
Thank a lot in advance!
Solution
computer-science formal-languages automata regular-language
computer-science formal-languages automata regular-language
edited yesterday
Joey Kilpatrick
1,070121
asked Nov 15 at 15:34
Avishai Yaniv
63
New contributor
Avishai Yaniv is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited yesterday
Joey Kilpatrick
1,070121
asked Nov 15 at 15:34
Avishai Yaniv
63
New contributor
Avishai Yaniv is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited yesterday
Joey Kilpatrick
1,070121
edited yesterday
Joey Kilpatrick
1,070121
edited yesterday
Joey Kilpatrick
1,070121
1,070121
asked Nov 15 at 15:34
Avishai Yaniv
63
New contributor
Avishai Yaniv is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Nov 15 at 15:34
Avishai Yaniv
63
asked Nov 15 at 15:34
Avishai Yaniv
63
63
New contributor
Avishai Yaniv is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Avishai Yaniv is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Avishai Yaniv is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
If $L$ is regular, then consider a DFA on $L$. Make two copies of it $D_1$ and $D_2$ and consider the DFA $D_1cup D_2$ letting the start state of $D_1$ be the start state of $D_1cup D_2$. Let $a_{(D_1)}$ and $b_{(D_1)}$ be states in $D_1$ and let $a_{(D_2)}$ and $b_{(D_2)}$ be the corresponding states in $D_2$. For all $a_{(D_1)}$,$b_{(D_1)}$,$a_{(D_2)}$ and $b_{(D_2)}$, if $sigmain Sigma$ and $a_{(D_1)}$ transitions to $b_{(D_1)}$ on $sigma$ in $D_1$, then we will add the transition $a_{(D_1)}$ to $b_{(D_2)}$ on any character except $sigma$ (i.e. $Sigma - sigma$) to $D_1cup D_2$. Remove the accept states from $D_1$ in $D_1cup D_2$. This NFA accepts exactly "$L$ almost".
The idea is that for any word in $L$, we want to make one "error" (the one letter off from the word in $L$). In our NFA, if a word is in $L$, then it will transition entirely within $D_1$ in $D_1cup D_2$. However, an "error" will then transition to the corresponding next state in $D_2$. This means that a word is in a state of $D_2$ in $D_1cup D_2$ only if it has an "error". We want to accept only the words that have one "error", so we remove the accept states from $D_1$ (since a word will only end in $D_1$ if it is in $L$).
answered Nov 15 at 16:13
Joey Kilpatrick
1,070121
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
If $L$ is regular, then consider a DFA on $L$. Make two copies of it $D_1$ and $D_2$ and consider the DFA $D_1cup D_2$ letting the start state of $D_1$ be the start state of $D_1cup D_2$. Let $a_{(D_1)}$ and $b_{(D_1)}$ be states in $D_1$ and let $a_{(D_2)}$ and $b_{(D_2)}$ be the corresponding states in $D_2$. For all $a_{(D_1)}$,$b_{(D_1)}$,$a_{(D_2)}$ and $b_{(D_2)}$, if $sigmain Sigma$ and $a_{(D_1)}$ transitions to $b_{(D_1)}$ on $sigma$ in $D_1$, then we will add the transition $a_{(D_1)}$ to $b_{(D_2)}$ on any character except $sigma$ (i.e. $Sigma - sigma$) to $D_1cup D_2$. Remove the accept states from $D_1$ in $D_1cup D_2$. This NFA accepts exactly "$L$ almost".
The idea is that for any word in $L$, we want to make one "error" (the one letter off from the word in $L$). In our NFA, if a word is in $L$, then it will transition entirely within $D_1$ in $D_1cup D_2$. However, an "error" will then transition to the corresponding next state in $D_2$. This means that a word is in a state of $D_2$ in $D_1cup D_2$ only if it has an "error". We want to accept only the words that have one "error", so we remove the accept states from $D_1$ (since a word will only end in $D_1$ if it is in $L$).
answered Nov 15 at 16:13
Joey Kilpatrick
1,070121
add a comment |
up vote
0
down vote
If $L$ is regular, then consider a DFA on $L$. Make two copies of it $D_1$ and $D_2$ and consider the DFA $D_1cup D_2$ letting the start state of $D_1$ be the start state of $D_1cup D_2$. Let $a_{(D_1)}$ and $b_{(D_1)}$ be states in $D_1$ and let $a_{(D_2)}$ and $b_{(D_2)}$ be the corresponding states in $D_2$. For all $a_{(D_1)}$,$b_{(D_1)}$,$a_{(D_2)}$ and $b_{(D_2)}$, if $sigmain Sigma$ and $a_{(D_1)}$ transitions to $b_{(D_1)}$ on $sigma$ in $D_1$, then we will add the transition $a_{(D_1)}$ to $b_{(D_2)}$ on any character except $sigma$ (i.e. $Sigma - sigma$) to $D_1cup D_2$. Remove the accept states from $D_1$ in $D_1cup D_2$. This NFA accepts exactly "$L$ almost".
The idea is that for any word in $L$, we want to make one "error" (the one letter off from the word in $L$). In our NFA, if a word is in $L$, then it will transition entirely within $D_1$ in $D_1cup D_2$. However, an "error" will then transition to the corresponding next state in $D_2$. This means that a word is in a state of $D_2$ in $D_1cup D_2$ only if it has an "error". We want to accept only the words that have one "error", so we remove the accept states from $D_1$ (since a word will only end in $D_1$ if it is in $L$).
answered Nov 15 at 16:13
Joey Kilpatrick
1,070121
add a comment |
up vote
0
down vote
up vote
0
down vote
If $L$ is regular, then consider a DFA on $L$. Make two copies of it $D_1$ and $D_2$ and consider the DFA $D_1cup D_2$ letting the start state of $D_1$ be the start state of $D_1cup D_2$. Let $a_{(D_1)}$ and $b_{(D_1)}$ be states in $D_1$ and let $a_{(D_2)}$ and $b_{(D_2)}$ be the corresponding states in $D_2$. For all $a_{(D_1)}$,$b_{(D_1)}$,$a_{(D_2)}$ and $b_{(D_2)}$, if $sigmain Sigma$ and $a_{(D_1)}$ transitions to $b_{(D_1)}$ on $sigma$ in $D_1$, then we will add the transition $a_{(D_1)}$ to $b_{(D_2)}$ on any character except $sigma$ (i.e. $Sigma - sigma$) to $D_1cup D_2$. Remove the accept states from $D_1$ in $D_1cup D_2$. This NFA accepts exactly "$L$ almost".
The idea is that for any word in $L$, we want to make one "error" (the one letter off from the word in $L$). In our NFA, if a word is in $L$, then it will transition entirely within $D_1$ in $D_1cup D_2$. However, an "error" will then transition to the corresponding next state in $D_2$. This means that a word is in a state of $D_2$ in $D_1cup D_2$ only if it has an "error". We want to accept only the words that have one "error", so we remove the accept states from $D_1$ (since a word will only end in $D_1$ if it is in $L$).
answered Nov 15 at 16:13
Joey Kilpatrick
1,070121
If $L$ is regular, then consider a DFA on $L$. Make two copies of it $D_1$ and $D_2$ and consider the DFA $D_1cup D_2$ letting the start state of $D_1$ be the start state of $D_1cup D_2$. Let $a_{(D_1)}$ and $b_{(D_1)}$ be states in $D_1$ and let $a_{(D_2)}$ and $b_{(D_2)}$ be the corresponding states in $D_2$. For all $a_{(D_1)}$,$b_{(D_1)}$,$a_{(D_2)}$ and $b_{(D_2)}$, if $sigmain Sigma$ and $a_{(D_1)}$ transitions to $b_{(D_1)}$ on $sigma$ in $D_1$, then we will add the transition $a_{(D_1)}$ to $b_{(D_2)}$ on any character except $sigma$ (i.e. $Sigma - sigma$) to $D_1cup D_2$. Remove the accept states from $D_1$ in $D_1cup D_2$. This NFA accepts exactly "$L$ almost".
The idea is that for any word in $L$, we want to make one "error" (the one letter off from the word in $L$). In our NFA, if a word is in $L$, then it will transition entirely within $D_1$ in $D_1cup D_2$. However, an "error" will then transition to the corresponding next state in $D_2$. This means that a word is in a state of $D_2$ in $D_1cup D_2$ only if it has an "error". We want to accept only the words that have one "error", so we remove the accept states from $D_1$ (since a word will only end in $D_1$ if it is in $L$).
answered Nov 15 at 16:13
Joey Kilpatrick
1,070121
answered Nov 15 at 16:13
Joey Kilpatrick
1,070121
answered Nov 15 at 16:13
Joey Kilpatrick
1,070121
answered Nov 15 at 16:13
Joey Kilpatrick
1,070121
1,070121
add a comment |
add a comment |
Avishai Yaniv is a new contributor. Be nice, and check out our Code of Conduct.
Avishai Yaniv is a new contributor. Be nice, and check out our Code of Conduct.
Avishai Yaniv is a new contributor. Be nice, and check out our Code of Conduct.
Avishai Yaniv is a new contributor. Be nice, and check out our Code of Conduct.
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%2f2999838%2fl-almost-is-regular%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
