How to create a DFA union transition dictionary based on transitions of DFA1 and DFA2
up vote
1
down vote
favorite
I have 2 DFA's, the transitions of which look as follows:
DFA1
{('q0', 'a'): 'q1', ...}
DFA2
{('q0', 'a'): 'q3',...}
As I understand, the delta of the unified DFA is supposed to look something like this:
{(('q0', 'a'): 'q1'), (('q0', 'a'): 'q3')),...and so on}
How can I merge these 2 dictionaries to create the tuples for the unified delta dictionary?
if I do DFA2.update(DFA1), the result is {('q0', 'a'): 'q1'}. Why doesn't this work and how do I make it work?
python dictionary dfa
asked Nov 21 at 18:21
nanachan
441520
add a comment |
up vote
1
down vote
favorite
I have 2 DFA's, the transitions of which look as follows:
DFA1
{('q0', 'a'): 'q1', ...}
DFA2
{('q0', 'a'): 'q3',...}
As I understand, the delta of the unified DFA is supposed to look something like this:
{(('q0', 'a'): 'q1'), (('q0', 'a'): 'q3')),...and so on}
How can I merge these 2 dictionaries to create the tuples for the unified delta dictionary?
if I do DFA2.update(DFA1), the result is {('q0', 'a'): 'q1'}. Why doesn't this work and how do I make it work?
python dictionary dfa
asked Nov 21 at 18:21
nanachan
441520
What's this notation:(('q0', 'a'): 'q1')? And is the "delta" simply all keys whose values are different in the 2 dictionaries?
– slider
Nov 21 at 18:30
'q0' is the start state, 'a' is the character on the arc, 'q1' is the state that 'q0' transitions to if 'a' is seen.
– nanachan
Nov 21 at 18:32
When DFA's are closed under union, the states of DFA1 and DFA2 make up tuples (product), i.e. (state1 of DFA1, state1 of DFA2), (state2 of DFA1, state2 of DFA2) and so forth. Delta is the transition function from state to state in a DFA. The union of DFA1 and DFA2 will have its delta as tuples such as (transition1 of DFA1, transition1 of DFA2) and so forth.
– nanachan
Nov 21 at 18:37
I simplified the question. The problem I am having is updating the transition dictionaries.
– nanachan
Nov 21 at 19:07
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I have 2 DFA's, the transitions of which look as follows:
DFA1
{('q0', 'a'): 'q1', ...}
DFA2
{('q0', 'a'): 'q3',...}
As I understand, the delta of the unified DFA is supposed to look something like this:
{(('q0', 'a'): 'q1'), (('q0', 'a'): 'q3')),...and so on}
How can I merge these 2 dictionaries to create the tuples for the unified delta dictionary?
if I do DFA2.update(DFA1), the result is {('q0', 'a'): 'q1'}. Why doesn't this work and how do I make it work?
python dictionary dfa
asked Nov 21 at 18:21
nanachan
441520
I have 2 DFA's, the transitions of which look as follows:
DFA1
{('q0', 'a'): 'q1', ...}
DFA2
{('q0', 'a'): 'q3',...}
As I understand, the delta of the unified DFA is supposed to look something like this:
{(('q0', 'a'): 'q1'), (('q0', 'a'): 'q3')),...and so on}
How can I merge these 2 dictionaries to create the tuples for the unified delta dictionary?
if I do DFA2.update(DFA1), the result is {('q0', 'a'): 'q1'}. Why doesn't this work and how do I make it work?
python dictionary dfa
python dictionary dfa
asked Nov 21 at 18:21
nanachan
441520
asked Nov 21 at 18:21
nanachan
441520
edited Nov 21 at 19:07
asked Nov 21 at 18:21
nanachan
441520
asked Nov 21 at 18:21
nanachan
441520
asked Nov 21 at 18:21
nanachan
441520
441520
What's this notation:(('q0', 'a'): 'q1')? And is the "delta" simply all keys whose values are different in the 2 dictionaries?
– slider
Nov 21 at 18:30
'q0' is the start state, 'a' is the character on the arc, 'q1' is the state that 'q0' transitions to if 'a' is seen.
– nanachan
Nov 21 at 18:32
When DFA's are closed under union, the states of DFA1 and DFA2 make up tuples (product), i.e. (state1 of DFA1, state1 of DFA2), (state2 of DFA1, state2 of DFA2) and so forth. Delta is the transition function from state to state in a DFA. The union of DFA1 and DFA2 will have its delta as tuples such as (transition1 of DFA1, transition1 of DFA2) and so forth.
– nanachan
Nov 21 at 18:37
I simplified the question. The problem I am having is updating the transition dictionaries.
– nanachan
Nov 21 at 19:07
add a comment |
What's this notation:(('q0', 'a'): 'q1')? And is the "delta" simply all keys whose values are different in the 2 dictionaries?
– slider
Nov 21 at 18:30
'q0' is the start state, 'a' is the character on the arc, 'q1' is the state that 'q0' transitions to if 'a' is seen.
– nanachan
Nov 21 at 18:32
When DFA's are closed under union, the states of DFA1 and DFA2 make up tuples (product), i.e. (state1 of DFA1, state1 of DFA2), (state2 of DFA1, state2 of DFA2) and so forth. Delta is the transition function from state to state in a DFA. The union of DFA1 and DFA2 will have its delta as tuples such as (transition1 of DFA1, transition1 of DFA2) and so forth.
– nanachan
Nov 21 at 18:37
I simplified the question. The problem I am having is updating the transition dictionaries.
– nanachan
Nov 21 at 19:07
What's this notation:
(('q0', 'a'): 'q1')? And is the "delta" simply all keys whose values are different in the 2 dictionaries?– slider
Nov 21 at 18:30
What's this notation:
(('q0', 'a'): 'q1')? And is the "delta" simply all keys whose values are different in the 2 dictionaries?– slider
Nov 21 at 18:30
'q0' is the start state, 'a' is the character on the arc, 'q1' is the state that 'q0' transitions to if 'a' is seen.
– nanachan
Nov 21 at 18:32
'q0' is the start state, 'a' is the character on the arc, 'q1' is the state that 'q0' transitions to if 'a' is seen.
– nanachan
Nov 21 at 18:32
When DFA's are closed under union, the states of DFA1 and DFA2 make up tuples (product), i.e. (state1 of DFA1, state1 of DFA2), (state2 of DFA1, state2 of DFA2) and so forth. Delta is the transition function from state to state in a DFA. The union of DFA1 and DFA2 will have its delta as tuples such as (transition1 of DFA1, transition1 of DFA2) and so forth.
– nanachan
Nov 21 at 18:37
When DFA's are closed under union, the states of DFA1 and DFA2 make up tuples (product), i.e. (state1 of DFA1, state1 of DFA2), (state2 of DFA1, state2 of DFA2) and so forth. Delta is the transition function from state to state in a DFA. The union of DFA1 and DFA2 will have its delta as tuples such as (transition1 of DFA1, transition1 of DFA2) and so forth.
– nanachan
Nov 21 at 18:37
I simplified the question. The problem I am having is updating the transition dictionaries.
– nanachan
Nov 21 at 19:07
I simplified the question. The problem I am having is updating the transition dictionaries.
– nanachan
Nov 21 at 19:07
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
I will suggest you to represent a DFA transition as a set of tuples instead of a key-value pair of dictionary. It's good as you will work on set operation in many algorithms related to DFA.
Example:
t1 = {('q0', 'a', 'q1'), ('q1', 'a', 'q2'), ...}
t2 = {('q0', 'a', 'q2'), ('q1', 'b', 'q2'), ...}
By t1.union(t2), you will get:
{('q0', 'a', 'q1'), ('q0', 'a', 'q2'), ('q1', 'a', 'q2'), ('q1', 'b', 'q2'), ...}
However if you insist to use dictionary, then you can refer to this thread.
answered Nov 28 at 0:22
bakka
723317
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
I will suggest you to represent a DFA transition as a set of tuples instead of a key-value pair of dictionary. It's good as you will work on set operation in many algorithms related to DFA.
Example:
t1 = {('q0', 'a', 'q1'), ('q1', 'a', 'q2'), ...}
t2 = {('q0', 'a', 'q2'), ('q1', 'b', 'q2'), ...}
By t1.union(t2), you will get:
{('q0', 'a', 'q1'), ('q0', 'a', 'q2'), ('q1', 'a', 'q2'), ('q1', 'b', 'q2'), ...}
However if you insist to use dictionary, then you can refer to this thread.
answered Nov 28 at 0:22
bakka
723317
add a comment |
up vote
0
down vote
I will suggest you to represent a DFA transition as a set of tuples instead of a key-value pair of dictionary. It's good as you will work on set operation in many algorithms related to DFA.
Example:
t1 = {('q0', 'a', 'q1'), ('q1', 'a', 'q2'), ...}
t2 = {('q0', 'a', 'q2'), ('q1', 'b', 'q2'), ...}
By t1.union(t2), you will get:
{('q0', 'a', 'q1'), ('q0', 'a', 'q2'), ('q1', 'a', 'q2'), ('q1', 'b', 'q2'), ...}
However if you insist to use dictionary, then you can refer to this thread.
answered Nov 28 at 0:22
bakka
723317
add a comment |
up vote
0
down vote
up vote
0
down vote
I will suggest you to represent a DFA transition as a set of tuples instead of a key-value pair of dictionary. It's good as you will work on set operation in many algorithms related to DFA.
Example:
t1 = {('q0', 'a', 'q1'), ('q1', 'a', 'q2'), ...}
t2 = {('q0', 'a', 'q2'), ('q1', 'b', 'q2'), ...}
By t1.union(t2), you will get:
{('q0', 'a', 'q1'), ('q0', 'a', 'q2'), ('q1', 'a', 'q2'), ('q1', 'b', 'q2'), ...}
However if you insist to use dictionary, then you can refer to this thread.
answered Nov 28 at 0:22
bakka
723317
I will suggest you to represent a DFA transition as a set of tuples instead of a key-value pair of dictionary. It's good as you will work on set operation in many algorithms related to DFA.
Example:
t1 = {('q0', 'a', 'q1'), ('q1', 'a', 'q2'), ...}
t2 = {('q0', 'a', 'q2'), ('q1', 'b', 'q2'), ...}
By t1.union(t2), you will get:
{('q0', 'a', 'q1'), ('q0', 'a', 'q2'), ('q1', 'a', 'q2'), ('q1', 'b', 'q2'), ...}
However if you insist to use dictionary, then you can refer to this thread.
answered Nov 28 at 0:22
bakka
723317
answered Nov 28 at 0:22
bakka
723317
answered Nov 28 at 0:22
bakka
723317
answered Nov 28 at 0:22
bakka
723317
723317
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- 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.
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%2fstackoverflow.com%2fquestions%2f53418331%2fhow-to-create-a-dfa-union-transition-dictionary-based-on-transitions-of-dfa1-and%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
What's this notation:
(('q0', 'a'): 'q1')? And is the "delta" simply all keys whose values are different in the 2 dictionaries?– slider
Nov 21 at 18:30
'q0' is the start state, 'a' is the character on the arc, 'q1' is the state that 'q0' transitions to if 'a' is seen.
– nanachan
Nov 21 at 18:32
When DFA's are closed under union, the states of DFA1 and DFA2 make up tuples (product), i.e. (state1 of DFA1, state1 of DFA2), (state2 of DFA1, state2 of DFA2) and so forth. Delta is the transition function from state to state in a DFA. The union of DFA1 and DFA2 will have its delta as tuples such as (transition1 of DFA1, transition1 of DFA2) and so forth.
– nanachan
Nov 21 at 18:37
I simplified the question. The problem I am having is updating the transition dictionaries.
– nanachan
Nov 21 at 19:07