Mixing
![If $(x_n)$ is bounded and diverges, then there exist two subsequences of $(x_n)$ that converge to different limits. [duplicate]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZCTB4-bb-s-32SAm6ytjzFOU06cH9o8q-a_wq_UnH6lcd8hvws23CmBWHM6g256LzTX9yK1EiCCzTC1NSgtxlNk_J9hdr9bA3tD0Nqntbl521j4bLAm_uXPANuWLBhcCKTKzns2gaUodx/s72-c/1.jpg)
equivalence of finite state and regular expression
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Consider the following theorem:
Theorem: If L=L(A) for some DFA A, then there is a regular expression R such that L=L(R)
Proof: Let A's states be: 1,2,3,....n for some integer n. Let $ R^k_ij$ be the name of regular expression whose language is the set of path from state i to state j in A, and it's intermediary nodes do not have number greater than k.
Basis: For k = 0, there are no intermediary nodes. So, when i != j, if the symbol for transition is a, then:
a) if there is no such symbol a, then: $ R^0_ij = $
b) if there is one then: $ R^k_ij = a$
c) if there are symbols $ a_1, a_2, ... a_k$ then $ R^0_ij = a_1+a_2...+a_k$
Induction: Suppose there is a path from state i to j that goes through no higher state than k. There are two possible cases.
1) The path does not go through state k at all. In this case, the label of the path is in the language of: $ R^(k-1)_ij$
#so far so good- no confusion upto this point
The biggest part of confusion is here in this statement no. 2
2) The path goes through state k at least once. It may be from i to k, k to k multiple times, and from k to j OR it may be from i to k and k to j. So, the regular expression would be: $ R^k-1_ik.(R^k-1_kk)^*.R^k-1_kj$
So, combining the regular expressions from 1 and 2 we get the regular expression from the automaton as:
$$ R^k_ij = R^k-1_ij + R^k-1_ik.(R^k-1_kk)^*.R^k-1_kj$$
The notation of $R^k_ij$ is that it should have no intermediary nodes greater than k, put another way, it may have less than *or equal to * k numbered states. So, in induction point number 2, we have the case where the intermediary nodes are allowed to touch k, though not pass higher than k. As it states, the path goes through k at least once, and yet, The regular expression is given as: $ R^k-1_ik.(R^k-1_kk)^*.R^k-1_kj$, in my opinion it should rather be: $ R^k_ik.(R^k_kk)^*.R^k_kj$. Where am I understanding this wrong, because, the former expression given in the proof, does not even touch k, where as my given expression would touch k.
Again, I could think it could be some print error given in the book, but all exercises have been based on this formula, so it should be accurate.
automata
asked Aug 1 at 10:59
bzal
306516
add a comment |Â
up vote
1
down vote
favorite
Consider the following theorem:
Theorem: If L=L(A) for some DFA A, then there is a regular expression R such that L=L(R)
Proof: Let A's states be: 1,2,3,....n for some integer n. Let $ R^k_ij$ be the name of regular expression whose language is the set of path from state i to state j in A, and it's intermediary nodes do not have number greater than k.
Basis: For k = 0, there are no intermediary nodes. So, when i != j, if the symbol for transition is a, then:
a) if there is no such symbol a, then: $ R^0_ij = $
b) if there is one then: $ R^k_ij = a$
c) if there are symbols $ a_1, a_2, ... a_k$ then $ R^0_ij = a_1+a_2...+a_k$
Induction: Suppose there is a path from state i to j that goes through no higher state than k. There are two possible cases.
1) The path does not go through state k at all. In this case, the label of the path is in the language of: $ R^(k-1)_ij$
#so far so good- no confusion upto this point
The biggest part of confusion is here in this statement no. 2
2) The path goes through state k at least once. It may be from i to k, k to k multiple times, and from k to j OR it may be from i to k and k to j. So, the regular expression would be: $ R^k-1_ik.(R^k-1_kk)^*.R^k-1_kj$
So, combining the regular expressions from 1 and 2 we get the regular expression from the automaton as:
$$ R^k_ij = R^k-1_ij + R^k-1_ik.(R^k-1_kk)^*.R^k-1_kj$$
The notation of $R^k_ij$ is that it should have no intermediary nodes greater than k, put another way, it may have less than *or equal to * k numbered states. So, in induction point number 2, we have the case where the intermediary nodes are allowed to touch k, though not pass higher than k. As it states, the path goes through k at least once, and yet, The regular expression is given as: $ R^k-1_ik.(R^k-1_kk)^*.R^k-1_kj$, in my opinion it should rather be: $ R^k_ik.(R^k_kk)^*.R^k_kj$. Where am I understanding this wrong, because, the former expression given in the proof, does not even touch k, where as my given expression would touch k.
Again, I could think it could be some print error given in the book, but all exercises have been based on this formula, so it should be accurate.
automata
asked Aug 1 at 10:59
bzal
306516
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Consider the following theorem:
Theorem: If L=L(A) for some DFA A, then there is a regular expression R such that L=L(R)
Proof: Let A's states be: 1,2,3,....n for some integer n. Let $ R^k_ij$ be the name of regular expression whose language is the set of path from state i to state j in A, and it's intermediary nodes do not have number greater than k.
Basis: For k = 0, there are no intermediary nodes. So, when i != j, if the symbol for transition is a, then:
a) if there is no such symbol a, then: $ R^0_ij = $
b) if there is one then: $ R^k_ij = a$
c) if there are symbols $ a_1, a_2, ... a_k$ then $ R^0_ij = a_1+a_2...+a_k$
Induction: Suppose there is a path from state i to j that goes through no higher state than k. There are two possible cases.
1) The path does not go through state k at all. In this case, the label of the path is in the language of: $ R^(k-1)_ij$
#so far so good- no confusion upto this point
The biggest part of confusion is here in this statement no. 2
2) The path goes through state k at least once. It may be from i to k, k to k multiple times, and from k to j OR it may be from i to k and k to j. So, the regular expression would be: $ R^k-1_ik.(R^k-1_kk)^*.R^k-1_kj$
So, combining the regular expressions from 1 and 2 we get the regular expression from the automaton as:
$$ R^k_ij = R^k-1_ij + R^k-1_ik.(R^k-1_kk)^*.R^k-1_kj$$
The notation of $R^k_ij$ is that it should have no intermediary nodes greater than k, put another way, it may have less than *or equal to * k numbered states. So, in induction point number 2, we have the case where the intermediary nodes are allowed to touch k, though not pass higher than k. As it states, the path goes through k at least once, and yet, The regular expression is given as: $ R^k-1_ik.(R^k-1_kk)^*.R^k-1_kj$, in my opinion it should rather be: $ R^k_ik.(R^k_kk)^*.R^k_kj$. Where am I understanding this wrong, because, the former expression given in the proof, does not even touch k, where as my given expression would touch k.
Again, I could think it could be some print error given in the book, but all exercises have been based on this formula, so it should be accurate.
automata
asked Aug 1 at 10:59
bzal
306516
Consider the following theorem:
Theorem: If L=L(A) for some DFA A, then there is a regular expression R such that L=L(R)
Proof: Let A's states be: 1,2,3,....n for some integer n. Let $ R^k_ij$ be the name of regular expression whose language is the set of path from state i to state j in A, and it's intermediary nodes do not have number greater than k.
Basis: For k = 0, there are no intermediary nodes. So, when i != j, if the symbol for transition is a, then:
a) if there is no such symbol a, then: $ R^0_ij = $
b) if there is one then: $ R^k_ij = a$
c) if there are symbols $ a_1, a_2, ... a_k$ then $ R^0_ij = a_1+a_2...+a_k$
Induction: Suppose there is a path from state i to j that goes through no higher state than k. There are two possible cases.
1) The path does not go through state k at all. In this case, the label of the path is in the language of: $ R^(k-1)_ij$
#so far so good- no confusion upto this point
The biggest part of confusion is here in this statement no. 2
2) The path goes through state k at least once. It may be from i to k, k to k multiple times, and from k to j OR it may be from i to k and k to j. So, the regular expression would be: $ R^k-1_ik.(R^k-1_kk)^*.R^k-1_kj$
So, combining the regular expressions from 1 and 2 we get the regular expression from the automaton as:
$$ R^k_ij = R^k-1_ij + R^k-1_ik.(R^k-1_kk)^*.R^k-1_kj$$
The notation of $R^k_ij$ is that it should have no intermediary nodes greater than k, put another way, it may have less than *or equal to * k numbered states. So, in induction point number 2, we have the case where the intermediary nodes are allowed to touch k, though not pass higher than k. As it states, the path goes through k at least once, and yet, The regular expression is given as: $ R^k-1_ik.(R^k-1_kk)^*.R^k-1_kj$, in my opinion it should rather be: $ R^k_ik.(R^k_kk)^*.R^k_kj$. Where am I understanding this wrong, because, the former expression given in the proof, does not even touch k, where as my given expression would touch k.
Again, I could think it could be some print error given in the book, but all exercises have been based on this formula, so it should be accurate.
automata
asked Aug 1 at 10:59
bzal
306516
asked Aug 1 at 10:59
bzal
306516
asked Aug 1 at 10:59
bzal
306516
asked Aug 1 at 10:59
bzal
306516
306516
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
Your suggested regular expression is correct, in the sense that it is equal to $R_ij^k$, but it's not very useful, because to construct $R_kk^k$ for example, you already need to know what $R_kk^k$ is!
The point of the proof is to induct on $k$, and to do this we cleverly define $R_ij^k$ in terms of expressions $R_mn^l$ where $l<k$, and we assume we already know how to construct such expressions. Otherwise we would have a circular definition.
answered Aug 1 at 11:13
Daniel Mroz
851314
so how does saying, "The path goes through state k at least once. " in the proof make sense?
– bzal
Aug 1 at 11:32
Because it's possible for a path from $i$ to $j$ to pass through $k$. In that case, we decompose the path into segments that start and/or end at $k$, but do not themselves pass through it: 1) the initial trip from $i$ to $k$, 2) some number of cycles at $k$, and 3) the final trip from $k$ to $j$.
– Daniel Mroz
Aug 1 at 11:50
I meant, if the states are all less than or equal to (k-1) then it's impossible to pass through k, so it doesn't really make sense in there?
– bzal
Aug 1 at 11:54
Plus a bit confused about the notion of intermediary, could you please see this diagram and answer a bit of issue I've mentioned there, please? (pasteboard.co/Hx9p26G.jpg)
– bzal
Aug 1 at 11:56
@bzal Ok, the notion of intermediate states is a key part of the proof. So the paths denoted by $R_ik^k-1$ do not have $k$ as an intermediate state, but they all end at $k$! Then when you compose this with the expression $(R_kk^k-1)^* R_kj^k-1$ you get a path that definitely goes through $k$. The important part is that we've described paths that have $k$ as an intermediate state in terms of paths that do not (although they start and/or end at $k$). This is what lets the induction work.
– Daniel Mroz
Aug 1 at 12:06
 |Â
show 8 more comments
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
Your suggested regular expression is correct, in the sense that it is equal to $R_ij^k$, but it's not very useful, because to construct $R_kk^k$ for example, you already need to know what $R_kk^k$ is!
The point of the proof is to induct on $k$, and to do this we cleverly define $R_ij^k$ in terms of expressions $R_mn^l$ where $l<k$, and we assume we already know how to construct such expressions. Otherwise we would have a circular definition.
answered Aug 1 at 11:13
Daniel Mroz
851314
so how does saying, "The path goes through state k at least once. " in the proof make sense?
– bzal
Aug 1 at 11:32
Because it's possible for a path from $i$ to $j$ to pass through $k$. In that case, we decompose the path into segments that start and/or end at $k$, but do not themselves pass through it: 1) the initial trip from $i$ to $k$, 2) some number of cycles at $k$, and 3) the final trip from $k$ to $j$.
– Daniel Mroz
Aug 1 at 11:50
I meant, if the states are all less than or equal to (k-1) then it's impossible to pass through k, so it doesn't really make sense in there?
– bzal
Aug 1 at 11:54
Plus a bit confused about the notion of intermediary, could you please see this diagram and answer a bit of issue I've mentioned there, please? (pasteboard.co/Hx9p26G.jpg)
– bzal
Aug 1 at 11:56
@bzal Ok, the notion of intermediate states is a key part of the proof. So the paths denoted by $R_ik^k-1$ do not have $k$ as an intermediate state, but they all end at $k$! Then when you compose this with the expression $(R_kk^k-1)^* R_kj^k-1$ you get a path that definitely goes through $k$. The important part is that we've described paths that have $k$ as an intermediate state in terms of paths that do not (although they start and/or end at $k$). This is what lets the induction work.
– Daniel Mroz
Aug 1 at 12:06
 |Â
show 8 more comments
up vote
1
down vote
Your suggested regular expression is correct, in the sense that it is equal to $R_ij^k$, but it's not very useful, because to construct $R_kk^k$ for example, you already need to know what $R_kk^k$ is!
The point of the proof is to induct on $k$, and to do this we cleverly define $R_ij^k$ in terms of expressions $R_mn^l$ where $l<k$, and we assume we already know how to construct such expressions. Otherwise we would have a circular definition.
answered Aug 1 at 11:13
Daniel Mroz
851314
so how does saying, "The path goes through state k at least once. " in the proof make sense?
– bzal
Aug 1 at 11:32
Because it's possible for a path from $i$ to $j$ to pass through $k$. In that case, we decompose the path into segments that start and/or end at $k$, but do not themselves pass through it: 1) the initial trip from $i$ to $k$, 2) some number of cycles at $k$, and 3) the final trip from $k$ to $j$.
– Daniel Mroz
Aug 1 at 11:50
I meant, if the states are all less than or equal to (k-1) then it's impossible to pass through k, so it doesn't really make sense in there?
– bzal
Aug 1 at 11:54
Plus a bit confused about the notion of intermediary, could you please see this diagram and answer a bit of issue I've mentioned there, please? (pasteboard.co/Hx9p26G.jpg)
– bzal
Aug 1 at 11:56
@bzal Ok, the notion of intermediate states is a key part of the proof. So the paths denoted by $R_ik^k-1$ do not have $k$ as an intermediate state, but they all end at $k$! Then when you compose this with the expression $(R_kk^k-1)^* R_kj^k-1$ you get a path that definitely goes through $k$. The important part is that we've described paths that have $k$ as an intermediate state in terms of paths that do not (although they start and/or end at $k$). This is what lets the induction work.
– Daniel Mroz
Aug 1 at 12:06
 |Â
show 8 more comments
up vote
1
down vote
up vote
1
down vote
Your suggested regular expression is correct, in the sense that it is equal to $R_ij^k$, but it's not very useful, because to construct $R_kk^k$ for example, you already need to know what $R_kk^k$ is!
The point of the proof is to induct on $k$, and to do this we cleverly define $R_ij^k$ in terms of expressions $R_mn^l$ where $l<k$, and we assume we already know how to construct such expressions. Otherwise we would have a circular definition.
answered Aug 1 at 11:13
Daniel Mroz
851314
Your suggested regular expression is correct, in the sense that it is equal to $R_ij^k$, but it's not very useful, because to construct $R_kk^k$ for example, you already need to know what $R_kk^k$ is!
The point of the proof is to induct on $k$, and to do this we cleverly define $R_ij^k$ in terms of expressions $R_mn^l$ where $l<k$, and we assume we already know how to construct such expressions. Otherwise we would have a circular definition.
answered Aug 1 at 11:13
Daniel Mroz
851314
answered Aug 1 at 11:13
Daniel Mroz
851314
answered Aug 1 at 11:13
Daniel Mroz
851314
answered Aug 1 at 11:13
Daniel Mroz
851314
851314
so how does saying, "The path goes through state k at least once. " in the proof make sense?
– bzal
Aug 1 at 11:32
Because it's possible for a path from $i$ to $j$ to pass through $k$. In that case, we decompose the path into segments that start and/or end at $k$, but do not themselves pass through it: 1) the initial trip from $i$ to $k$, 2) some number of cycles at $k$, and 3) the final trip from $k$ to $j$.
– Daniel Mroz
Aug 1 at 11:50
I meant, if the states are all less than or equal to (k-1) then it's impossible to pass through k, so it doesn't really make sense in there?
– bzal
Aug 1 at 11:54
Plus a bit confused about the notion of intermediary, could you please see this diagram and answer a bit of issue I've mentioned there, please? (pasteboard.co/Hx9p26G.jpg)
– bzal
Aug 1 at 11:56
@bzal Ok, the notion of intermediate states is a key part of the proof. So the paths denoted by $R_ik^k-1$ do not have $k$ as an intermediate state, but they all end at $k$! Then when you compose this with the expression $(R_kk^k-1)^* R_kj^k-1$ you get a path that definitely goes through $k$. The important part is that we've described paths that have $k$ as an intermediate state in terms of paths that do not (although they start and/or end at $k$). This is what lets the induction work.
– Daniel Mroz
Aug 1 at 12:06
 |Â
show 8 more comments
so how does saying, "The path goes through state k at least once. " in the proof make sense?
– bzal
Aug 1 at 11:32
Because it's possible for a path from $i$ to $j$ to pass through $k$. In that case, we decompose the path into segments that start and/or end at $k$, but do not themselves pass through it: 1) the initial trip from $i$ to $k$, 2) some number of cycles at $k$, and 3) the final trip from $k$ to $j$.
– Daniel Mroz
Aug 1 at 11:50
I meant, if the states are all less than or equal to (k-1) then it's impossible to pass through k, so it doesn't really make sense in there?
– bzal
Aug 1 at 11:54
Plus a bit confused about the notion of intermediary, could you please see this diagram and answer a bit of issue I've mentioned there, please? (pasteboard.co/Hx9p26G.jpg)
– bzal
Aug 1 at 11:56
@bzal Ok, the notion of intermediate states is a key part of the proof. So the paths denoted by $R_ik^k-1$ do not have $k$ as an intermediate state, but they all end at $k$! Then when you compose this with the expression $(R_kk^k-1)^* R_kj^k-1$ you get a path that definitely goes through $k$. The important part is that we've described paths that have $k$ as an intermediate state in terms of paths that do not (although they start and/or end at $k$). This is what lets the induction work.
– Daniel Mroz
Aug 1 at 12:06
so how does saying, "The path goes through state k at least once. " in the proof make sense?
– bzal
Aug 1 at 11:32
so how does saying, "The path goes through state k at least once. " in the proof make sense?
– bzal
Aug 1 at 11:32
Because it's possible for a path from $i$ to $j$ to pass through $k$. In that case, we decompose the path into segments that start and/or end at $k$, but do not themselves pass through it: 1) the initial trip from $i$ to $k$, 2) some number of cycles at $k$, and 3) the final trip from $k$ to $j$.
– Daniel Mroz
Aug 1 at 11:50
Because it's possible for a path from $i$ to $j$ to pass through $k$. In that case, we decompose the path into segments that start and/or end at $k$, but do not themselves pass through it: 1) the initial trip from $i$ to $k$, 2) some number of cycles at $k$, and 3) the final trip from $k$ to $j$.
– Daniel Mroz
Aug 1 at 11:50
I meant, if the states are all less than or equal to (k-1) then it's impossible to pass through k, so it doesn't really make sense in there?
– bzal
Aug 1 at 11:54
I meant, if the states are all less than or equal to (k-1) then it's impossible to pass through k, so it doesn't really make sense in there?
– bzal
Aug 1 at 11:54
Plus a bit confused about the notion of intermediary, could you please see this diagram and answer a bit of issue I've mentioned there, please? (pasteboard.co/Hx9p26G.jpg)
– bzal
Aug 1 at 11:56
Plus a bit confused about the notion of intermediary, could you please see this diagram and answer a bit of issue I've mentioned there, please? (pasteboard.co/Hx9p26G.jpg)
– bzal
Aug 1 at 11:56
@bzal Ok, the notion of intermediate states is a key part of the proof. So the paths denoted by $R_ik^k-1$ do not have $k$ as an intermediate state, but they all end at $k$! Then when you compose this with the expression $(R_kk^k-1)^* R_kj^k-1$ you get a path that definitely goes through $k$. The important part is that we've described paths that have $k$ as an intermediate state in terms of paths that do not (although they start and/or end at $k$). This is what lets the induction work.
– Daniel Mroz
Aug 1 at 12:06
@bzal Ok, the notion of intermediate states is a key part of the proof. So the paths denoted by $R_ik^k-1$ do not have $k$ as an intermediate state, but they all end at $k$! Then when you compose this with the expression $(R_kk^k-1)^* R_kj^k-1$ you get a path that definitely goes through $k$. The important part is that we've described paths that have $k$ as an intermediate state in terms of paths that do not (although they start and/or end at $k$). This is what lets the induction work.
– Daniel Mroz
Aug 1 at 12:06
 |Â
show 8 more comments
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2868950%2fequivalence-of-finite-state-and-regular-expression%23new-answer', 'question_page');
);
Post as a guest
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
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
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