Mixing
DFA accepts only one state
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Consider the NFA that accepts the language L such that:
L= second last symbol in w is one
Now, the NFA diagram for this is:
Now the corresponding DFA diagram for this would be:
Now, lets take an instance. Say we're at q0 state and we take an input 0, from the NFA we can see that we may be now at the q0 state or q1 state, and represent this in the DFA as q'01. This is where the confusion is, the resultant is a subset of the powerset of NFA's states.
By the definition of DFA, an input must result to only one state, so, when converting a NFA to DFA, why is it that the resulting state is a set and not just one state like q1 or q2 but like: q0, q1?
computer-science formal-languages automata
edited Jul 25 at 17:36
Math1000
18.4k31444
asked Jul 25 at 16:54
bzal
306516
add a comment |Â
up vote
1
down vote
favorite
Consider the NFA that accepts the language L such that:
L= second last symbol in w is one
Now, the NFA diagram for this is:
Now the corresponding DFA diagram for this would be:
Now, lets take an instance. Say we're at q0 state and we take an input 0, from the NFA we can see that we may be now at the q0 state or q1 state, and represent this in the DFA as q'01. This is where the confusion is, the resultant is a subset of the powerset of NFA's states.
By the definition of DFA, an input must result to only one state, so, when converting a NFA to DFA, why is it that the resulting state is a set and not just one state like q1 or q2 but like: q0, q1?
computer-science formal-languages automata
edited Jul 25 at 17:36
Math1000
18.4k31444
asked Jul 25 at 16:54
bzal
306516
2
It looks to me like the NFA accepts strings whose next-to-last symbol is $0$.
– saulspatz
Jul 25 at 17:11
1
Yes, but $q_0, q_1$ will be a single state of the DFA, so what's the problem?
– saulspatz
Jul 25 at 17:17
@saulspatz , sorry for the late remark but, my confusion is, that from a input we end up into the state: q0, q1 then, how is this one state? Are we in q0? or in q1? If not we're in both right?
– bzal
Jul 26 at 5:38
$q_0, q_1$ are not states in the DFA, so we are in neither of them. You can think of the state in the DFA as the set of all NFA states we might be in on receiving the same input.
– saulspatz
Jul 26 at 14:24
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Consider the NFA that accepts the language L such that:
L= second last symbol in w is one
Now, the NFA diagram for this is:
Now the corresponding DFA diagram for this would be:
Now, lets take an instance. Say we're at q0 state and we take an input 0, from the NFA we can see that we may be now at the q0 state or q1 state, and represent this in the DFA as q'01. This is where the confusion is, the resultant is a subset of the powerset of NFA's states.
By the definition of DFA, an input must result to only one state, so, when converting a NFA to DFA, why is it that the resulting state is a set and not just one state like q1 or q2 but like: q0, q1?
computer-science formal-languages automata
edited Jul 25 at 17:36
Math1000
18.4k31444
asked Jul 25 at 16:54
bzal
306516
Consider the NFA that accepts the language L such that:
L= second last symbol in w is one
Now, the NFA diagram for this is:
Now the corresponding DFA diagram for this would be:
Now, lets take an instance. Say we're at q0 state and we take an input 0, from the NFA we can see that we may be now at the q0 state or q1 state, and represent this in the DFA as q'01. This is where the confusion is, the resultant is a subset of the powerset of NFA's states.
By the definition of DFA, an input must result to only one state, so, when converting a NFA to DFA, why is it that the resulting state is a set and not just one state like q1 or q2 but like: q0, q1?
computer-science formal-languages automata
edited Jul 25 at 17:36
Math1000
18.4k31444
asked Jul 25 at 16:54
bzal
306516
edited Jul 25 at 17:36
Math1000
18.4k31444
edited Jul 25 at 17:36
Math1000
18.4k31444
edited Jul 25 at 17:36
Math1000
18.4k31444
18.4k31444
asked Jul 25 at 16:54
bzal
306516
asked Jul 25 at 16:54
bzal
306516
asked Jul 25 at 16:54
bzal
306516
306516
2
It looks to me like the NFA accepts strings whose next-to-last symbol is $0$.
– saulspatz
Jul 25 at 17:11
1
Yes, but $q_0, q_1$ will be a single state of the DFA, so what's the problem?
– saulspatz
Jul 25 at 17:17
@saulspatz , sorry for the late remark but, my confusion is, that from a input we end up into the state: q0, q1 then, how is this one state? Are we in q0? or in q1? If not we're in both right?
– bzal
Jul 26 at 5:38
$q_0, q_1$ are not states in the DFA, so we are in neither of them. You can think of the state in the DFA as the set of all NFA states we might be in on receiving the same input.
– saulspatz
Jul 26 at 14:24
add a comment |Â
2
It looks to me like the NFA accepts strings whose next-to-last symbol is $0$.
– saulspatz
Jul 25 at 17:11
1
Yes, but $q_0, q_1$ will be a single state of the DFA, so what's the problem?
– saulspatz
Jul 25 at 17:17
@saulspatz , sorry for the late remark but, my confusion is, that from a input we end up into the state: q0, q1 then, how is this one state? Are we in q0? or in q1? If not we're in both right?
– bzal
Jul 26 at 5:38
$q_0, q_1$ are not states in the DFA, so we are in neither of them. You can think of the state in the DFA as the set of all NFA states we might be in on receiving the same input.
– saulspatz
Jul 26 at 14:24
2
2
It looks to me like the NFA accepts strings whose next-to-last symbol is $0$.
– saulspatz
Jul 25 at 17:11
It looks to me like the NFA accepts strings whose next-to-last symbol is $0$.
– saulspatz
Jul 25 at 17:11
1
1
Yes, but $q_0, q_1$ will be a single state of the DFA, so what's the problem?
– saulspatz
Jul 25 at 17:17
Yes, but $q_0, q_1$ will be a single state of the DFA, so what's the problem?
– saulspatz
Jul 25 at 17:17
@saulspatz , sorry for the late remark but, my confusion is, that from a input we end up into the state: q0, q1 then, how is this one state? Are we in q0? or in q1? If not we're in both right?
– bzal
Jul 26 at 5:38
@saulspatz , sorry for the late remark but, my confusion is, that from a input we end up into the state: q0, q1 then, how is this one state? Are we in q0? or in q1? If not we're in both right?
– bzal
Jul 26 at 5:38
$q_0, q_1$ are not states in the DFA, so we are in neither of them. You can think of the state in the DFA as the set of all NFA states we might be in on receiving the same input.
– saulspatz
Jul 26 at 14:24
$q_0, q_1$ are not states in the DFA, so we are in neither of them. You can think of the state in the DFA as the set of all NFA states we might be in on receiving the same input.
– saulspatz
Jul 26 at 14:24
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
I understand where your confusion comes from. The proof that DFA's and NFA's are equivalent in terms of the languages they accept, involves something called "subset construction". In order to deterministically simulate all the states and transitions from the NFA, one has to build a DFA that so-to-say "lives" on the powerset of the state set $Q $.
However, it does not matter that our resulting states in the newly constructed DFA $D = langle mathcalP(Q),delta,q_0,Frangle $ are all sets, since the transition function $delta : mathcalP(Q) rightarrow mathcalP(Q)$ is still a real function (i.e it takes a state of $D$ - in this case a set - and returns exactly one other state (or in this case a set).)
Theoretically, the set of states of your original NFA could also be sets, or a set containing sets. It does not really matter what mathematical objects the set of states $Q$ consists of. The transition function of the DFA just has to be deterministic. If you go a bit deeper into the fundamentals of mathematics, you will see that even natural numbers can be seen as sets, for example the Von Neumann construction of the natural numbers works pretty much like this:
$$0 = emptyset\
1 = emptyset\
2 = emptyset, emptyset$$
answered Jul 25 at 20:14
GreenLogic
1701210
I can see the part here being deterministic, i.e. the transition function takes input to only one output, but it's still very unclear to me when we say that we're in state q'01 i.e. we're in q0, q1 then what state are we in? are we in state q0? or are we in state q1? If we're in both, how come it's deterministic?
– bzal
Jul 26 at 5:51
@bzal You should think of the state $q_01$ as a new state that nothing to do with the set $q_0,q_1$, besides it simulating a specific transition of the original NFA. You are neither in $q_0$, nor in $q_1$. You are in a completely new automaton with completely different states. (which has the property that it accepts the same language as your NFA).
– GreenLogic
Jul 26 at 13:23
1
@bzal In order to make a DFA out of an NFA, you have to generalise in a way. Let's say the states represent which country you are in right now: $q_0$ stands for Germany and $q_1$ for the Netherlands. In the corresponding DFA, let the states now represent continents and not countries anymore. Then you could think of $q_01$ as standing for the continent Europe and your transition function of the DFA takes one continent and returns another one, regardless of countries.
– GreenLogic
Jul 26 at 13:27
wow, that's a completely new understanding for me, and it's hard to grasp. How come there is no relation between the two FAs? I mean they have the same states,and following a DFA on inputs leads to exactly the same state as NFA... So, why no relation? In particular, I've been trying to answer this question: .... .. please see below:
– bzal
Jul 27 at 5:14
Let's say in the NFA transition that state q0 is a state where 'w' the string has a zero, q1 is the state where 'w' as a 0 followed directly by 1 and q2 is a state where a 1 is followed directly by another 1. And let q2 be the accepting state, Now, for some transition diagram, we converted the NFA to DFA and in the time created a state called q'012 , So, how do we informally describe this state? Is this the state, where we can say the string now has a 0? or a 0 followed by one? or a string ending with 011?
– bzal
Jul 27 at 5:14
 |Â
show 3 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
accepted
I understand where your confusion comes from. The proof that DFA's and NFA's are equivalent in terms of the languages they accept, involves something called "subset construction". In order to deterministically simulate all the states and transitions from the NFA, one has to build a DFA that so-to-say "lives" on the powerset of the state set $Q $.
However, it does not matter that our resulting states in the newly constructed DFA $D = langle mathcalP(Q),delta,q_0,Frangle $ are all sets, since the transition function $delta : mathcalP(Q) rightarrow mathcalP(Q)$ is still a real function (i.e it takes a state of $D$ - in this case a set - and returns exactly one other state (or in this case a set).)
Theoretically, the set of states of your original NFA could also be sets, or a set containing sets. It does not really matter what mathematical objects the set of states $Q$ consists of. The transition function of the DFA just has to be deterministic. If you go a bit deeper into the fundamentals of mathematics, you will see that even natural numbers can be seen as sets, for example the Von Neumann construction of the natural numbers works pretty much like this:
$$0 = emptyset\
1 = emptyset\
2 = emptyset, emptyset$$
answered Jul 25 at 20:14
GreenLogic
1701210
I can see the part here being deterministic, i.e. the transition function takes input to only one output, but it's still very unclear to me when we say that we're in state q'01 i.e. we're in q0, q1 then what state are we in? are we in state q0? or are we in state q1? If we're in both, how come it's deterministic?
– bzal
Jul 26 at 5:51
@bzal You should think of the state $q_01$ as a new state that nothing to do with the set $q_0,q_1$, besides it simulating a specific transition of the original NFA. You are neither in $q_0$, nor in $q_1$. You are in a completely new automaton with completely different states. (which has the property that it accepts the same language as your NFA).
– GreenLogic
Jul 26 at 13:23
1
@bzal In order to make a DFA out of an NFA, you have to generalise in a way. Let's say the states represent which country you are in right now: $q_0$ stands for Germany and $q_1$ for the Netherlands. In the corresponding DFA, let the states now represent continents and not countries anymore. Then you could think of $q_01$ as standing for the continent Europe and your transition function of the DFA takes one continent and returns another one, regardless of countries.
– GreenLogic
Jul 26 at 13:27
wow, that's a completely new understanding for me, and it's hard to grasp. How come there is no relation between the two FAs? I mean they have the same states,and following a DFA on inputs leads to exactly the same state as NFA... So, why no relation? In particular, I've been trying to answer this question: .... .. please see below:
– bzal
Jul 27 at 5:14
Let's say in the NFA transition that state q0 is a state where 'w' the string has a zero, q1 is the state where 'w' as a 0 followed directly by 1 and q2 is a state where a 1 is followed directly by another 1. And let q2 be the accepting state, Now, for some transition diagram, we converted the NFA to DFA and in the time created a state called q'012 , So, how do we informally describe this state? Is this the state, where we can say the string now has a 0? or a 0 followed by one? or a string ending with 011?
– bzal
Jul 27 at 5:14
 |Â
show 3 more comments
up vote
1
down vote
accepted
I understand where your confusion comes from. The proof that DFA's and NFA's are equivalent in terms of the languages they accept, involves something called "subset construction". In order to deterministically simulate all the states and transitions from the NFA, one has to build a DFA that so-to-say "lives" on the powerset of the state set $Q $.
However, it does not matter that our resulting states in the newly constructed DFA $D = langle mathcalP(Q),delta,q_0,Frangle $ are all sets, since the transition function $delta : mathcalP(Q) rightarrow mathcalP(Q)$ is still a real function (i.e it takes a state of $D$ - in this case a set - and returns exactly one other state (or in this case a set).)
Theoretically, the set of states of your original NFA could also be sets, or a set containing sets. It does not really matter what mathematical objects the set of states $Q$ consists of. The transition function of the DFA just has to be deterministic. If you go a bit deeper into the fundamentals of mathematics, you will see that even natural numbers can be seen as sets, for example the Von Neumann construction of the natural numbers works pretty much like this:
$$0 = emptyset\
1 = emptyset\
2 = emptyset, emptyset$$
answered Jul 25 at 20:14
GreenLogic
1701210
I can see the part here being deterministic, i.e. the transition function takes input to only one output, but it's still very unclear to me when we say that we're in state q'01 i.e. we're in q0, q1 then what state are we in? are we in state q0? or are we in state q1? If we're in both, how come it's deterministic?
– bzal
Jul 26 at 5:51
@bzal You should think of the state $q_01$ as a new state that nothing to do with the set $q_0,q_1$, besides it simulating a specific transition of the original NFA. You are neither in $q_0$, nor in $q_1$. You are in a completely new automaton with completely different states. (which has the property that it accepts the same language as your NFA).
– GreenLogic
Jul 26 at 13:23
1
@bzal In order to make a DFA out of an NFA, you have to generalise in a way. Let's say the states represent which country you are in right now: $q_0$ stands for Germany and $q_1$ for the Netherlands. In the corresponding DFA, let the states now represent continents and not countries anymore. Then you could think of $q_01$ as standing for the continent Europe and your transition function of the DFA takes one continent and returns another one, regardless of countries.
– GreenLogic
Jul 26 at 13:27
wow, that's a completely new understanding for me, and it's hard to grasp. How come there is no relation between the two FAs? I mean they have the same states,and following a DFA on inputs leads to exactly the same state as NFA... So, why no relation? In particular, I've been trying to answer this question: .... .. please see below:
– bzal
Jul 27 at 5:14
Let's say in the NFA transition that state q0 is a state where 'w' the string has a zero, q1 is the state where 'w' as a 0 followed directly by 1 and q2 is a state where a 1 is followed directly by another 1. And let q2 be the accepting state, Now, for some transition diagram, we converted the NFA to DFA and in the time created a state called q'012 , So, how do we informally describe this state? Is this the state, where we can say the string now has a 0? or a 0 followed by one? or a string ending with 011?
– bzal
Jul 27 at 5:14
 |Â
show 3 more comments
up vote
1
down vote
accepted
up vote
1
down vote
accepted
I understand where your confusion comes from. The proof that DFA's and NFA's are equivalent in terms of the languages they accept, involves something called "subset construction". In order to deterministically simulate all the states and transitions from the NFA, one has to build a DFA that so-to-say "lives" on the powerset of the state set $Q $.
However, it does not matter that our resulting states in the newly constructed DFA $D = langle mathcalP(Q),delta,q_0,Frangle $ are all sets, since the transition function $delta : mathcalP(Q) rightarrow mathcalP(Q)$ is still a real function (i.e it takes a state of $D$ - in this case a set - and returns exactly one other state (or in this case a set).)
Theoretically, the set of states of your original NFA could also be sets, or a set containing sets. It does not really matter what mathematical objects the set of states $Q$ consists of. The transition function of the DFA just has to be deterministic. If you go a bit deeper into the fundamentals of mathematics, you will see that even natural numbers can be seen as sets, for example the Von Neumann construction of the natural numbers works pretty much like this:
$$0 = emptyset\
1 = emptyset\
2 = emptyset, emptyset$$
answered Jul 25 at 20:14
GreenLogic
1701210
I understand where your confusion comes from. The proof that DFA's and NFA's are equivalent in terms of the languages they accept, involves something called "subset construction". In order to deterministically simulate all the states and transitions from the NFA, one has to build a DFA that so-to-say "lives" on the powerset of the state set $Q $.
However, it does not matter that our resulting states in the newly constructed DFA $D = langle mathcalP(Q),delta,q_0,Frangle $ are all sets, since the transition function $delta : mathcalP(Q) rightarrow mathcalP(Q)$ is still a real function (i.e it takes a state of $D$ - in this case a set - and returns exactly one other state (or in this case a set).)
Theoretically, the set of states of your original NFA could also be sets, or a set containing sets. It does not really matter what mathematical objects the set of states $Q$ consists of. The transition function of the DFA just has to be deterministic. If you go a bit deeper into the fundamentals of mathematics, you will see that even natural numbers can be seen as sets, for example the Von Neumann construction of the natural numbers works pretty much like this:
$$0 = emptyset\
1 = emptyset\
2 = emptyset, emptyset$$
answered Jul 25 at 20:14
GreenLogic
1701210
edited Jul 25 at 20:20
answered Jul 25 at 20:14
GreenLogic
1701210
answered Jul 25 at 20:14
GreenLogic
1701210
answered Jul 25 at 20:14
GreenLogic
1701210
1701210
I can see the part here being deterministic, i.e. the transition function takes input to only one output, but it's still very unclear to me when we say that we're in state q'01 i.e. we're in q0, q1 then what state are we in? are we in state q0? or are we in state q1? If we're in both, how come it's deterministic?
– bzal
Jul 26 at 5:51
@bzal You should think of the state $q_01$ as a new state that nothing to do with the set $q_0,q_1$, besides it simulating a specific transition of the original NFA. You are neither in $q_0$, nor in $q_1$. You are in a completely new automaton with completely different states. (which has the property that it accepts the same language as your NFA).
– GreenLogic
Jul 26 at 13:23
1
@bzal In order to make a DFA out of an NFA, you have to generalise in a way. Let's say the states represent which country you are in right now: $q_0$ stands for Germany and $q_1$ for the Netherlands. In the corresponding DFA, let the states now represent continents and not countries anymore. Then you could think of $q_01$ as standing for the continent Europe and your transition function of the DFA takes one continent and returns another one, regardless of countries.
– GreenLogic
Jul 26 at 13:27
wow, that's a completely new understanding for me, and it's hard to grasp. How come there is no relation between the two FAs? I mean they have the same states,and following a DFA on inputs leads to exactly the same state as NFA... So, why no relation? In particular, I've been trying to answer this question: .... .. please see below:
– bzal
Jul 27 at 5:14
Let's say in the NFA transition that state q0 is a state where 'w' the string has a zero, q1 is the state where 'w' as a 0 followed directly by 1 and q2 is a state where a 1 is followed directly by another 1. And let q2 be the accepting state, Now, for some transition diagram, we converted the NFA to DFA and in the time created a state called q'012 , So, how do we informally describe this state? Is this the state, where we can say the string now has a 0? or a 0 followed by one? or a string ending with 011?
– bzal
Jul 27 at 5:14
 |Â
show 3 more comments
I can see the part here being deterministic, i.e. the transition function takes input to only one output, but it's still very unclear to me when we say that we're in state q'01 i.e. we're in q0, q1 then what state are we in? are we in state q0? or are we in state q1? If we're in both, how come it's deterministic?
– bzal
Jul 26 at 5:51
@bzal You should think of the state $q_01$ as a new state that nothing to do with the set $q_0,q_1$, besides it simulating a specific transition of the original NFA. You are neither in $q_0$, nor in $q_1$. You are in a completely new automaton with completely different states. (which has the property that it accepts the same language as your NFA).
– GreenLogic
Jul 26 at 13:23
1
@bzal In order to make a DFA out of an NFA, you have to generalise in a way. Let's say the states represent which country you are in right now: $q_0$ stands for Germany and $q_1$ for the Netherlands. In the corresponding DFA, let the states now represent continents and not countries anymore. Then you could think of $q_01$ as standing for the continent Europe and your transition function of the DFA takes one continent and returns another one, regardless of countries.
– GreenLogic
Jul 26 at 13:27
wow, that's a completely new understanding for me, and it's hard to grasp. How come there is no relation between the two FAs? I mean they have the same states,and following a DFA on inputs leads to exactly the same state as NFA... So, why no relation? In particular, I've been trying to answer this question: .... .. please see below:
– bzal
Jul 27 at 5:14
Let's say in the NFA transition that state q0 is a state where 'w' the string has a zero, q1 is the state where 'w' as a 0 followed directly by 1 and q2 is a state where a 1 is followed directly by another 1. And let q2 be the accepting state, Now, for some transition diagram, we converted the NFA to DFA and in the time created a state called q'012 , So, how do we informally describe this state? Is this the state, where we can say the string now has a 0? or a 0 followed by one? or a string ending with 011?
– bzal
Jul 27 at 5:14
I can see the part here being deterministic, i.e. the transition function takes input to only one output, but it's still very unclear to me when we say that we're in state q'01 i.e. we're in q0, q1 then what state are we in? are we in state q0? or are we in state q1? If we're in both, how come it's deterministic?
– bzal
Jul 26 at 5:51
I can see the part here being deterministic, i.e. the transition function takes input to only one output, but it's still very unclear to me when we say that we're in state q'01 i.e. we're in q0, q1 then what state are we in? are we in state q0? or are we in state q1? If we're in both, how come it's deterministic?
– bzal
Jul 26 at 5:51
@bzal You should think of the state $q_01$ as a new state that nothing to do with the set $q_0,q_1$, besides it simulating a specific transition of the original NFA. You are neither in $q_0$, nor in $q_1$. You are in a completely new automaton with completely different states. (which has the property that it accepts the same language as your NFA).
– GreenLogic
Jul 26 at 13:23
@bzal You should think of the state $q_01$ as a new state that nothing to do with the set $q_0,q_1$, besides it simulating a specific transition of the original NFA. You are neither in $q_0$, nor in $q_1$. You are in a completely new automaton with completely different states. (which has the property that it accepts the same language as your NFA).
– GreenLogic
Jul 26 at 13:23
1
1
@bzal In order to make a DFA out of an NFA, you have to generalise in a way. Let's say the states represent which country you are in right now: $q_0$ stands for Germany and $q_1$ for the Netherlands. In the corresponding DFA, let the states now represent continents and not countries anymore. Then you could think of $q_01$ as standing for the continent Europe and your transition function of the DFA takes one continent and returns another one, regardless of countries.
– GreenLogic
Jul 26 at 13:27
@bzal In order to make a DFA out of an NFA, you have to generalise in a way. Let's say the states represent which country you are in right now: $q_0$ stands for Germany and $q_1$ for the Netherlands. In the corresponding DFA, let the states now represent continents and not countries anymore. Then you could think of $q_01$ as standing for the continent Europe and your transition function of the DFA takes one continent and returns another one, regardless of countries.
– GreenLogic
Jul 26 at 13:27
wow, that's a completely new understanding for me, and it's hard to grasp. How come there is no relation between the two FAs? I mean they have the same states,and following a DFA on inputs leads to exactly the same state as NFA... So, why no relation? In particular, I've been trying to answer this question: .... .. please see below:
– bzal
Jul 27 at 5:14
wow, that's a completely new understanding for me, and it's hard to grasp. How come there is no relation between the two FAs? I mean they have the same states,and following a DFA on inputs leads to exactly the same state as NFA... So, why no relation? In particular, I've been trying to answer this question: .... .. please see below:
– bzal
Jul 27 at 5:14
Let's say in the NFA transition that state q0 is a state where 'w' the string has a zero, q1 is the state where 'w' as a 0 followed directly by 1 and q2 is a state where a 1 is followed directly by another 1. And let q2 be the accepting state, Now, for some transition diagram, we converted the NFA to DFA and in the time created a state called q'012 , So, how do we informally describe this state? Is this the state, where we can say the string now has a 0? or a 0 followed by one? or a string ending with 011?
– bzal
Jul 27 at 5:14
Let's say in the NFA transition that state q0 is a state where 'w' the string has a zero, q1 is the state where 'w' as a 0 followed directly by 1 and q2 is a state where a 1 is followed directly by another 1. And let q2 be the accepting state, Now, for some transition diagram, we converted the NFA to DFA and in the time created a state called q'012 , So, how do we informally describe this state? Is this the state, where we can say the string now has a 0? or a 0 followed by one? or a string ending with 011?
– bzal
Jul 27 at 5:14
 |Â
show 3 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%2f2862617%2fdfa-accepts-only-one-state%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
2
It looks to me like the NFA accepts strings whose next-to-last symbol is $0$.
– saulspatz
Jul 25 at 17:11
1
Yes, but $q_0, q_1$ will be a single state of the DFA, so what's the problem?
– saulspatz
Jul 25 at 17:17
@saulspatz , sorry for the late remark but, my confusion is, that from a input we end up into the state: q0, q1 then, how is this one state? Are we in q0? or in q1? If not we're in both right?
– bzal
Jul 26 at 5:38
$q_0, q_1$ are not states in the DFA, so we are in neither of them. You can think of the state in the DFA as the set of all NFA states we might be in on receiving the same input.
– saulspatz
Jul 26 at 14:24