Automata | Prove that if $L$ is regular than $half(L)$ is regular too The 2019 Stack Overflow Developer Survey Results Are InAutomata|The mid 1/3 of regular language is still regularAutomata|f(L) take the length of a regular language's prefix to the length of the restIs this language regular ? [automata]Proving that $L= a^nb^n, nge 0$ is not a regular language.Possible solution for Sipser 1.63Languages and their Regular Expressions - AutomataWhich automata recognizes the language defined by the regular expressionproving that a regular language can be accepted by a fast finite automatonProve that if $L$ is regular, then $f(L)$ is regular tooFinite Automata for regular expressionAre regular languages closed by a full-shuffle operation?Regular Expression VS Finite Automata
What information about me do stores get via my credit card?
How did passengers keep warm on sail ships?
Getting crown tickets for Statue of Liberty
Can I have a signal generator on while it's not connected?
Loose spokes after only a few rides
Why are there uneven bright areas in this photo of black hole?
What do hard-Brexiteers want with respect to the Irish border?
Did Scotland spend $250,000 for the slogan "Welcome to Scotland"?
How can I have a shield and a way of attacking with a ranged weapon at the same time?
How to obtain a position of last non-zero element
Match Roman Numerals
Why doesn't shell automatically fix "useless use of cat"?
I am an eight letter word. What am I?
The phrase "to the numbers born"?
Correct punctuation for showing a character's confusion
How to display lines in a file like ls displays files in a directory?
Is there a way to generate a uniformly distributed point on a sphere from a fixed amount of random real numbers?
Short story: child made less intelligent and less attractive
"as much details as you can remember"
What is this sharp, curved notch on my knife for?
If my opponent casts Ultimate Price on my Phantasmal Bear, can I save it by casting Snap or Curfew?
For what reasons would an animal species NOT cross a *horizontal* land bridge?
Why isn't the circumferential light around the M87 black hole's event horizon symmetric?
Can a flute soloist sit?
Automata | Prove that if $L$ is regular than $half(L)$ is regular too
The 2019 Stack Overflow Developer Survey Results Are InAutomata|The mid 1/3 of regular language is still regularAutomata|f(L) take the length of a regular language's prefix to the length of the restIs this language regular ? [automata]Proving that $L= a^nb^n, nge 0$ is not a regular language.Possible solution for Sipser 1.63Languages and their Regular Expressions - AutomataWhich automata recognizes the language defined by the regular expressionproving that a regular language can be accepted by a fast finite automatonProve that if $L$ is regular, then $f(L)$ is regular tooFinite Automata for regular expressionAre regular languages closed by a full-shuffle operation?Regular Expression VS Finite Automata
$begingroup$
I've see couple of approaches to this kind of questions yet I have no clue how to approach this one.
Let L be regular language, and let $half(L)$ be:
$half(L) = u mid uv in L s.t. $.
Prove that if $L$ is regular then $half(L)$ is regular too.
I tried to make a new regular language, $Even(L)$ that recognizes all the even words in $L$ (due to the fact that if we want to slice in half the total length must be even) and from there to "capture" the half words.
But I still think it isn't quite correct.
Would like to understand the logic behind a proper solution rather than just the solution :)
Thanks!
automata regular-language regular-expressions
edited Mar 24 at 2:59
J.-E. Pin
18.6k21754
asked Nov 21 '15 at 13:39
AviadAviad
11815
$endgroup$
|
show 4 more comments
$begingroup$
I've see couple of approaches to this kind of questions yet I have no clue how to approach this one.
Let L be regular language, and let $half(L)$ be:
$half(L) = u mid uv in L s.t. $.
Prove that if $L$ is regular then $half(L)$ is regular too.
I tried to make a new regular language, $Even(L)$ that recognizes all the even words in $L$ (due to the fact that if we want to slice in half the total length must be even) and from there to "capture" the half words.
But I still think it isn't quite correct.
Would like to understand the logic behind a proper solution rather than just the solution :)
Thanks!
automata regular-language regular-expressions
edited Mar 24 at 2:59
J.-E. Pin
18.6k21754
asked Nov 21 '15 at 13:39
AviadAviad
11815
$endgroup$
$begingroup$
infolab.stanford.edu/~ullman/ialcsols/sol4.html, exercise 4.2.8
$endgroup$
– Henno Brandsma
Nov 21 '15 at 13:49
$begingroup$
@HennoBrandsma do you mind further elaborating about the solution? I didn't get the part about the accepting states and that they should be reached by epsilon-moves from any point
$endgroup$
– Aviad
Nov 21 '15 at 13:55
$begingroup$
Basically you construct an automaton for half $L$ from one for $L$.
$endgroup$
– Henno Brandsma
Nov 21 '15 at 13:56
$begingroup$
This part I've got, I just didn't get the logic behind switching between the duplicates
$endgroup$
– Aviad
Nov 21 '15 at 13:59
$begingroup$
Are you allowed to use NFA's as well?
$endgroup$
– Henno Brandsma
Nov 21 '15 at 14:14
|
show 4 more comments
$begingroup$
I've see couple of approaches to this kind of questions yet I have no clue how to approach this one.
Let L be regular language, and let $half(L)$ be:
$half(L) = u mid uv in L s.t. $.
Prove that if $L$ is regular then $half(L)$ is regular too.
I tried to make a new regular language, $Even(L)$ that recognizes all the even words in $L$ (due to the fact that if we want to slice in half the total length must be even) and from there to "capture" the half words.
But I still think it isn't quite correct.
Would like to understand the logic behind a proper solution rather than just the solution :)
Thanks!
automata regular-language regular-expressions
edited Mar 24 at 2:59
J.-E. Pin
18.6k21754
asked Nov 21 '15 at 13:39
AviadAviad
11815
$endgroup$
I've see couple of approaches to this kind of questions yet I have no clue how to approach this one.
Let L be regular language, and let $half(L)$ be:
$half(L) = u mid uv in L s.t. $.
Prove that if $L$ is regular then $half(L)$ is regular too.
I tried to make a new regular language, $Even(L)$ that recognizes all the even words in $L$ (due to the fact that if we want to slice in half the total length must be even) and from there to "capture" the half words.
But I still think it isn't quite correct.
Would like to understand the logic behind a proper solution rather than just the solution :)
Thanks!
automata regular-language regular-expressions
automata regular-language regular-expressions
edited Mar 24 at 2:59
J.-E. Pin
18.6k21754
asked Nov 21 '15 at 13:39
AviadAviad
11815
edited Mar 24 at 2:59
J.-E. Pin
18.6k21754
asked Nov 21 '15 at 13:39
AviadAviad
11815
edited Mar 24 at 2:59
J.-E. Pin
18.6k21754
edited Mar 24 at 2:59
J.-E. Pin
18.6k21754
edited Mar 24 at 2:59
J.-E. Pin
18.6k21754
18.6k21754
asked Nov 21 '15 at 13:39
AviadAviad
11815
asked Nov 21 '15 at 13:39
AviadAviad
11815
asked Nov 21 '15 at 13:39
AviadAviad
11815
11815
$begingroup$
infolab.stanford.edu/~ullman/ialcsols/sol4.html, exercise 4.2.8
$endgroup$
– Henno Brandsma
Nov 21 '15 at 13:49
$begingroup$
@HennoBrandsma do you mind further elaborating about the solution? I didn't get the part about the accepting states and that they should be reached by epsilon-moves from any point
$endgroup$
– Aviad
Nov 21 '15 at 13:55
$begingroup$
Basically you construct an automaton for half $L$ from one for $L$.
$endgroup$
– Henno Brandsma
Nov 21 '15 at 13:56
$begingroup$
This part I've got, I just didn't get the logic behind switching between the duplicates
$endgroup$
– Aviad
Nov 21 '15 at 13:59
$begingroup$
Are you allowed to use NFA's as well?
$endgroup$
– Henno Brandsma
Nov 21 '15 at 14:14
|
show 4 more comments
$begingroup$
infolab.stanford.edu/~ullman/ialcsols/sol4.html, exercise 4.2.8
$endgroup$
– Henno Brandsma
Nov 21 '15 at 13:49
$begingroup$
@HennoBrandsma do you mind further elaborating about the solution? I didn't get the part about the accepting states and that they should be reached by epsilon-moves from any point
$endgroup$
– Aviad
Nov 21 '15 at 13:55
$begingroup$
Basically you construct an automaton for half $L$ from one for $L$.
$endgroup$
– Henno Brandsma
Nov 21 '15 at 13:56
$begingroup$
This part I've got, I just didn't get the logic behind switching between the duplicates
$endgroup$
– Aviad
Nov 21 '15 at 13:59
$begingroup$
Are you allowed to use NFA's as well?
$endgroup$
– Henno Brandsma
Nov 21 '15 at 14:14
$begingroup$
infolab.stanford.edu/~ullman/ialcsols/sol4.html, exercise 4.2.8
$endgroup$
– Henno Brandsma
Nov 21 '15 at 13:49
$begingroup$
infolab.stanford.edu/~ullman/ialcsols/sol4.html, exercise 4.2.8
$endgroup$
– Henno Brandsma
Nov 21 '15 at 13:49
$begingroup$
@HennoBrandsma do you mind further elaborating about the solution? I didn't get the part about the accepting states and that they should be reached by epsilon-moves from any point
$endgroup$
– Aviad
Nov 21 '15 at 13:55
$begingroup$
@HennoBrandsma do you mind further elaborating about the solution? I didn't get the part about the accepting states and that they should be reached by epsilon-moves from any point
$endgroup$
– Aviad
Nov 21 '15 at 13:55
$begingroup$
Basically you construct an automaton for half $L$ from one for $L$.
$endgroup$
– Henno Brandsma
Nov 21 '15 at 13:56
$begingroup$
Basically you construct an automaton for half $L$ from one for $L$.
$endgroup$
– Henno Brandsma
Nov 21 '15 at 13:56
$begingroup$
This part I've got, I just didn't get the logic behind switching between the duplicates
$endgroup$
– Aviad
Nov 21 '15 at 13:59
$begingroup$
This part I've got, I just didn't get the logic behind switching between the duplicates
$endgroup$
– Aviad
Nov 21 '15 at 13:59
$begingroup$
Are you allowed to use NFA's as well?
$endgroup$
– Henno Brandsma
Nov 21 '15 at 14:14
$begingroup$
Are you allowed to use NFA's as well?
$endgroup$
– Henno Brandsma
Nov 21 '15 at 14:14
|
show 4 more comments
1 Answer
1
active
oldest
votes
$begingroup$
Let $A = (delta_A, Q, q_0, F)$ be a DFA for $L$ (in some alphabet $Sigma$).
Then define $B$ as follows:
- The states $Q_B$ of $B$ are of the form $[q,S]$ where $q in Q$ and $S subseteq Q$.
- The initial state of $B$ is $[q_0, F]$.
- $delta_B([q,S],a) = [delta_A(q,a), T]$ where $T = p in Q: exists b in Sigma: exists p' in S: delta_A(p,b) = p' $
- The accepting states of $B$ are $F_B = [q,S] : q in S $.
Then we have the following invariant by construction: all reachable states $[q,S]$ after some input are such that $q$ is the state that $A$ would be in after reading that input, and the states in $S$ are all those states such that there is a path from that state to an accepting state (in $A$) that has the same length as the input that was read.
This holds for the initial state (no input, so the only state $A$ could be in is $q_0$ and the only accepting states on no input are those in $F$).
The way the transition rule is defined also upholds the relation: the first part just does what $A$ would have done on that extra letter, and we update the states so that there is a path to an accepting state that is 1 step longer. We could formally prove it by induction on the length of the input.
And when we are in a state $[q,S]$ with $q in S$ after reading some input $w_1$, we know that $q$ is the state of $A$ after reading $w_1$ and as $q in S$ there is some input $w_2$ with $|w_1| = |w_2|$ that induces a path from $q$ to an accepting state, which means that $w_1w_2 in L$, and so $w_1 in operatornamehalf(L)$.
(source: this solution, a bit reformulated)
answered Nov 21 '15 at 14:50
Henno BrandsmaHenno Brandsma
116k349127
$endgroup$
$begingroup$
Thanks :) Still working on fully understading this. on the delta, you've used 'small' s (rather than big), you indicate by that that s belongs to S ? or the string we've read so far?
$endgroup$
– Aviad
Nov 21 '15 at 15:07
1
$begingroup$
I corrected that typo
$endgroup$
– Henno Brandsma
Nov 21 '15 at 16:12
$begingroup$
Thanks! Another one to fix is the brackets in the initial state of B (wrote () rather than [] )
$endgroup$
– Aviad
Nov 22 '15 at 0:33
1
$begingroup$
I think this solution is the projection of the cross product of two NFAs. One is the actual NFA accepting L. Another one is the reverse NFA i.e. the NFA of L with arrows in the opposite direction, along with a new state which acts as the starting state and such that you can reach any state in F just by the empty string. After taking the cross product you declare the final state as the diagonal elements i.e. states of the fo (d,d). Then if (x,y) is accepted by this NFA x.(-y) is accepted by the DFA of L where (-y) is the reverse of y. The answer is the projection in the first coordinate.
$endgroup$
– Arka Ghosh
Aug 30 '18 at 8:07
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%2f1539658%2fautomata-prove-that-if-l-is-regular-than-halfl-is-regular-too%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 $A = (delta_A, Q, q_0, F)$ be a DFA for $L$ (in some alphabet $Sigma$).
Then define $B$ as follows:
- The states $Q_B$ of $B$ are of the form $[q,S]$ where $q in Q$ and $S subseteq Q$.
- The initial state of $B$ is $[q_0, F]$.
- $delta_B([q,S],a) = [delta_A(q,a), T]$ where $T = p in Q: exists b in Sigma: exists p' in S: delta_A(p,b) = p' $
- The accepting states of $B$ are $F_B = [q,S] : q in S $.
Then we have the following invariant by construction: all reachable states $[q,S]$ after some input are such that $q$ is the state that $A$ would be in after reading that input, and the states in $S$ are all those states such that there is a path from that state to an accepting state (in $A$) that has the same length as the input that was read.
This holds for the initial state (no input, so the only state $A$ could be in is $q_0$ and the only accepting states on no input are those in $F$).
The way the transition rule is defined also upholds the relation: the first part just does what $A$ would have done on that extra letter, and we update the states so that there is a path to an accepting state that is 1 step longer. We could formally prove it by induction on the length of the input.
And when we are in a state $[q,S]$ with $q in S$ after reading some input $w_1$, we know that $q$ is the state of $A$ after reading $w_1$ and as $q in S$ there is some input $w_2$ with $|w_1| = |w_2|$ that induces a path from $q$ to an accepting state, which means that $w_1w_2 in L$, and so $w_1 in operatornamehalf(L)$.
(source: this solution, a bit reformulated)
answered Nov 21 '15 at 14:50
Henno BrandsmaHenno Brandsma
116k349127
$endgroup$
$begingroup$
Thanks :) Still working on fully understading this. on the delta, you've used 'small' s (rather than big), you indicate by that that s belongs to S ? or the string we've read so far?
$endgroup$
– Aviad
Nov 21 '15 at 15:07
1
$begingroup$
I corrected that typo
$endgroup$
– Henno Brandsma
Nov 21 '15 at 16:12
$begingroup$
Thanks! Another one to fix is the brackets in the initial state of B (wrote () rather than [] )
$endgroup$
– Aviad
Nov 22 '15 at 0:33
1
$begingroup$
I think this solution is the projection of the cross product of two NFAs. One is the actual NFA accepting L. Another one is the reverse NFA i.e. the NFA of L with arrows in the opposite direction, along with a new state which acts as the starting state and such that you can reach any state in F just by the empty string. After taking the cross product you declare the final state as the diagonal elements i.e. states of the fo (d,d). Then if (x,y) is accepted by this NFA x.(-y) is accepted by the DFA of L where (-y) is the reverse of y. The answer is the projection in the first coordinate.
$endgroup$
– Arka Ghosh
Aug 30 '18 at 8:07
add a comment |
$begingroup$
Let $A = (delta_A, Q, q_0, F)$ be a DFA for $L$ (in some alphabet $Sigma$).
Then define $B$ as follows:
- The states $Q_B$ of $B$ are of the form $[q,S]$ where $q in Q$ and $S subseteq Q$.
- The initial state of $B$ is $[q_0, F]$.
- $delta_B([q,S],a) = [delta_A(q,a), T]$ where $T = p in Q: exists b in Sigma: exists p' in S: delta_A(p,b) = p' $
- The accepting states of $B$ are $F_B = [q,S] : q in S $.
Then we have the following invariant by construction: all reachable states $[q,S]$ after some input are such that $q$ is the state that $A$ would be in after reading that input, and the states in $S$ are all those states such that there is a path from that state to an accepting state (in $A$) that has the same length as the input that was read.
This holds for the initial state (no input, so the only state $A$ could be in is $q_0$ and the only accepting states on no input are those in $F$).
The way the transition rule is defined also upholds the relation: the first part just does what $A$ would have done on that extra letter, and we update the states so that there is a path to an accepting state that is 1 step longer. We could formally prove it by induction on the length of the input.
And when we are in a state $[q,S]$ with $q in S$ after reading some input $w_1$, we know that $q$ is the state of $A$ after reading $w_1$ and as $q in S$ there is some input $w_2$ with $|w_1| = |w_2|$ that induces a path from $q$ to an accepting state, which means that $w_1w_2 in L$, and so $w_1 in operatornamehalf(L)$.
(source: this solution, a bit reformulated)
answered Nov 21 '15 at 14:50
Henno BrandsmaHenno Brandsma
116k349127
$endgroup$
$begingroup$
Thanks :) Still working on fully understading this. on the delta, you've used 'small' s (rather than big), you indicate by that that s belongs to S ? or the string we've read so far?
$endgroup$
– Aviad
Nov 21 '15 at 15:07
1
$begingroup$
I corrected that typo
$endgroup$
– Henno Brandsma
Nov 21 '15 at 16:12
$begingroup$
Thanks! Another one to fix is the brackets in the initial state of B (wrote () rather than [] )
$endgroup$
– Aviad
Nov 22 '15 at 0:33
1
$begingroup$
I think this solution is the projection of the cross product of two NFAs. One is the actual NFA accepting L. Another one is the reverse NFA i.e. the NFA of L with arrows in the opposite direction, along with a new state which acts as the starting state and such that you can reach any state in F just by the empty string. After taking the cross product you declare the final state as the diagonal elements i.e. states of the fo (d,d). Then if (x,y) is accepted by this NFA x.(-y) is accepted by the DFA of L where (-y) is the reverse of y. The answer is the projection in the first coordinate.
$endgroup$
– Arka Ghosh
Aug 30 '18 at 8:07
add a comment |
$begingroup$
Let $A = (delta_A, Q, q_0, F)$ be a DFA for $L$ (in some alphabet $Sigma$).
Then define $B$ as follows:
- The states $Q_B$ of $B$ are of the form $[q,S]$ where $q in Q$ and $S subseteq Q$.
- The initial state of $B$ is $[q_0, F]$.
- $delta_B([q,S],a) = [delta_A(q,a), T]$ where $T = p in Q: exists b in Sigma: exists p' in S: delta_A(p,b) = p' $
- The accepting states of $B$ are $F_B = [q,S] : q in S $.
Then we have the following invariant by construction: all reachable states $[q,S]$ after some input are such that $q$ is the state that $A$ would be in after reading that input, and the states in $S$ are all those states such that there is a path from that state to an accepting state (in $A$) that has the same length as the input that was read.
This holds for the initial state (no input, so the only state $A$ could be in is $q_0$ and the only accepting states on no input are those in $F$).
The way the transition rule is defined also upholds the relation: the first part just does what $A$ would have done on that extra letter, and we update the states so that there is a path to an accepting state that is 1 step longer. We could formally prove it by induction on the length of the input.
And when we are in a state $[q,S]$ with $q in S$ after reading some input $w_1$, we know that $q$ is the state of $A$ after reading $w_1$ and as $q in S$ there is some input $w_2$ with $|w_1| = |w_2|$ that induces a path from $q$ to an accepting state, which means that $w_1w_2 in L$, and so $w_1 in operatornamehalf(L)$.
(source: this solution, a bit reformulated)
answered Nov 21 '15 at 14:50
Henno BrandsmaHenno Brandsma
116k349127
$endgroup$
Let $A = (delta_A, Q, q_0, F)$ be a DFA for $L$ (in some alphabet $Sigma$).
Then define $B$ as follows:
- The states $Q_B$ of $B$ are of the form $[q,S]$ where $q in Q$ and $S subseteq Q$.
- The initial state of $B$ is $[q_0, F]$.
- $delta_B([q,S],a) = [delta_A(q,a), T]$ where $T = p in Q: exists b in Sigma: exists p' in S: delta_A(p,b) = p' $
- The accepting states of $B$ are $F_B = [q,S] : q in S $.
Then we have the following invariant by construction: all reachable states $[q,S]$ after some input are such that $q$ is the state that $A$ would be in after reading that input, and the states in $S$ are all those states such that there is a path from that state to an accepting state (in $A$) that has the same length as the input that was read.
This holds for the initial state (no input, so the only state $A$ could be in is $q_0$ and the only accepting states on no input are those in $F$).
The way the transition rule is defined also upholds the relation: the first part just does what $A$ would have done on that extra letter, and we update the states so that there is a path to an accepting state that is 1 step longer. We could formally prove it by induction on the length of the input.
And when we are in a state $[q,S]$ with $q in S$ after reading some input $w_1$, we know that $q$ is the state of $A$ after reading $w_1$ and as $q in S$ there is some input $w_2$ with $|w_1| = |w_2|$ that induces a path from $q$ to an accepting state, which means that $w_1w_2 in L$, and so $w_1 in operatornamehalf(L)$.
(source: this solution, a bit reformulated)
answered Nov 21 '15 at 14:50
Henno BrandsmaHenno Brandsma
116k349127
edited Nov 22 '15 at 5:29
answered Nov 21 '15 at 14:50
Henno BrandsmaHenno Brandsma
116k349127
answered Nov 21 '15 at 14:50
Henno BrandsmaHenno Brandsma
116k349127
answered Nov 21 '15 at 14:50
Henno BrandsmaHenno Brandsma
116k349127
116k349127
$begingroup$
Thanks :) Still working on fully understading this. on the delta, you've used 'small' s (rather than big), you indicate by that that s belongs to S ? or the string we've read so far?
$endgroup$
– Aviad
Nov 21 '15 at 15:07
1
$begingroup$
I corrected that typo
$endgroup$
– Henno Brandsma
Nov 21 '15 at 16:12
$begingroup$
Thanks! Another one to fix is the brackets in the initial state of B (wrote () rather than [] )
$endgroup$
– Aviad
Nov 22 '15 at 0:33
1
$begingroup$
I think this solution is the projection of the cross product of two NFAs. One is the actual NFA accepting L. Another one is the reverse NFA i.e. the NFA of L with arrows in the opposite direction, along with a new state which acts as the starting state and such that you can reach any state in F just by the empty string. After taking the cross product you declare the final state as the diagonal elements i.e. states of the fo (d,d). Then if (x,y) is accepted by this NFA x.(-y) is accepted by the DFA of L where (-y) is the reverse of y. The answer is the projection in the first coordinate.
$endgroup$
– Arka Ghosh
Aug 30 '18 at 8:07
add a comment |
$begingroup$
Thanks :) Still working on fully understading this. on the delta, you've used 'small' s (rather than big), you indicate by that that s belongs to S ? or the string we've read so far?
$endgroup$
– Aviad
Nov 21 '15 at 15:07
1
$begingroup$
I corrected that typo
$endgroup$
– Henno Brandsma
Nov 21 '15 at 16:12
$begingroup$
Thanks! Another one to fix is the brackets in the initial state of B (wrote () rather than [] )
$endgroup$
– Aviad
Nov 22 '15 at 0:33
1
$begingroup$
I think this solution is the projection of the cross product of two NFAs. One is the actual NFA accepting L. Another one is the reverse NFA i.e. the NFA of L with arrows in the opposite direction, along with a new state which acts as the starting state and such that you can reach any state in F just by the empty string. After taking the cross product you declare the final state as the diagonal elements i.e. states of the fo (d,d). Then if (x,y) is accepted by this NFA x.(-y) is accepted by the DFA of L where (-y) is the reverse of y. The answer is the projection in the first coordinate.
$endgroup$
– Arka Ghosh
Aug 30 '18 at 8:07
$begingroup$
Thanks :) Still working on fully understading this. on the delta, you've used 'small' s (rather than big), you indicate by that that s belongs to S ? or the string we've read so far?
$endgroup$
– Aviad
Nov 21 '15 at 15:07
$begingroup$
Thanks :) Still working on fully understading this. on the delta, you've used 'small' s (rather than big), you indicate by that that s belongs to S ? or the string we've read so far?
$endgroup$
– Aviad
Nov 21 '15 at 15:07
1
1
$begingroup$
I corrected that typo
$endgroup$
– Henno Brandsma
Nov 21 '15 at 16:12
$begingroup$
I corrected that typo
$endgroup$
– Henno Brandsma
Nov 21 '15 at 16:12
$begingroup$
Thanks! Another one to fix is the brackets in the initial state of B (wrote () rather than [] )
$endgroup$
– Aviad
Nov 22 '15 at 0:33
$begingroup$
Thanks! Another one to fix is the brackets in the initial state of B (wrote () rather than [] )
$endgroup$
– Aviad
Nov 22 '15 at 0:33
1
1
$begingroup$
I think this solution is the projection of the cross product of two NFAs. One is the actual NFA accepting L. Another one is the reverse NFA i.e. the NFA of L with arrows in the opposite direction, along with a new state which acts as the starting state and such that you can reach any state in F just by the empty string. After taking the cross product you declare the final state as the diagonal elements i.e. states of the fo (d,d). Then if (x,y) is accepted by this NFA x.(-y) is accepted by the DFA of L where (-y) is the reverse of y. The answer is the projection in the first coordinate.
$endgroup$
– Arka Ghosh
Aug 30 '18 at 8:07
$begingroup$
I think this solution is the projection of the cross product of two NFAs. One is the actual NFA accepting L. Another one is the reverse NFA i.e. the NFA of L with arrows in the opposite direction, along with a new state which acts as the starting state and such that you can reach any state in F just by the empty string. After taking the cross product you declare the final state as the diagonal elements i.e. states of the fo (d,d). Then if (x,y) is accepted by this NFA x.(-y) is accepted by the DFA of L where (-y) is the reverse of y. The answer is the projection in the first coordinate.
$endgroup$
– Arka Ghosh
Aug 30 '18 at 8:07
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%2f1539658%2fautomata-prove-that-if-l-is-regular-than-halfl-is-regular-too%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$
infolab.stanford.edu/~ullman/ialcsols/sol4.html, exercise 4.2.8
$endgroup$
– Henno Brandsma
Nov 21 '15 at 13:49
$begingroup$
@HennoBrandsma do you mind further elaborating about the solution? I didn't get the part about the accepting states and that they should be reached by epsilon-moves from any point
$endgroup$
– Aviad
Nov 21 '15 at 13:55
$begingroup$
Basically you construct an automaton for half $L$ from one for $L$.
$endgroup$
– Henno Brandsma
Nov 21 '15 at 13:56
$begingroup$
This part I've got, I just didn't get the logic behind switching between the duplicates
$endgroup$
– Aviad
Nov 21 '15 at 13:59
$begingroup$
Are you allowed to use NFA's as well?
$endgroup$
– Henno Brandsma
Nov 21 '15 at 14:14