How to create a DFA union transition dictionary based on transitions of DFA1 and DFA2
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 '18 at 18:21
nanachannanachan
441620
add a comment |
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 '18 at 18:21
nanachannanachan
441620
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 '18 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 '18 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 '18 at 18:37
I simplified the question. The problem I am having is updating the transition dictionaries.
– nanachan
Nov 21 '18 at 19:07
add a comment |
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 '18 at 18:21
nanachannanachan
441620
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 '18 at 18:21
nanachannanachan
441620
asked Nov 21 '18 at 18:21
nanachannanachan
441620
edited Nov 21 '18 at 19:07
nanachan
asked Nov 21 '18 at 18:21
nanachannanachan
441620
asked Nov 21 '18 at 18:21
nanachannanachan
441620
asked Nov 21 '18 at 18:21
nanachannanachan
441620
441620
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 '18 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 '18 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 '18 at 18:37
I simplified the question. The problem I am having is updating the transition dictionaries.
– nanachan
Nov 21 '18 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 '18 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 '18 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 '18 at 18:37
I simplified the question. The problem I am having is updating the transition dictionaries.
– nanachan
Nov 21 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 at 18:37
I simplified the question. The problem I am having is updating the transition dictionaries.
– nanachan
Nov 21 '18 at 19:07
I simplified the question. The problem I am having is updating the transition dictionaries.
– nanachan
Nov 21 '18 at 19:07
add a comment |
1 Answer
1
active
oldest
votes
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 '18 at 0:22
bakkabakka
759317
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
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
},
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%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
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
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 '18 at 0:22
bakkabakka
759317
add a comment |
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 '18 at 0:22
bakkabakka
759317
add a comment |
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 '18 at 0:22
bakkabakka
759317
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 '18 at 0:22
bakkabakka
759317
answered Nov 28 '18 at 0:22
bakkabakka
759317
answered Nov 28 '18 at 0:22
bakkabakka
759317
answered Nov 28 '18 at 0:22
bakkabakka
759317
759317
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.
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 '18 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 '18 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 '18 at 18:37
I simplified the question. The problem I am having is updating the transition dictionaries.
– nanachan
Nov 21 '18 at 19:07