1
$\begingroup$

I am currently converting this NFA to a DFA

enter image description here

I have come up with the following DFA:

        0      1
->A    {A}    {B}
  B    {CA} 
*CA    {A}    {AB}
 AB    {CA}   {B}

Although, I have no idea what to put for B. In the NFA, upon the B receiving 1 input, it goes nowhere - assumable unaccepted by the NFA. Do I send the DFA to a new, dead state upon receiving input 1 whilst in B?

I can try it:

        0      1
->A    {A}    {B}
  B    {CA}   {}
*CA    {A}    {AB}
 AB    {CA}   {B}
 {}    {}     {}

But is this correct by the rules of DFA?

$\endgroup$
  • $\begingroup$ Have you tried that? Did it work? By the way, can you give a reference to or name the way you convert NFA to DFA? $\endgroup$ – John L. Nov 22 '18 at 5:22
  • $\begingroup$ Sorry, I am using Subset Construction Method. $\endgroup$ – NBray Nov 22 '18 at 5:26
1
$\begingroup$

Creating a new sink state is perfectly fine. The empty set is also a subset of all states.

In most DFA diagrams this state is omitted for simplicity.

$\endgroup$
  • $\begingroup$ I dispute "most". All the sources I'm familiar with require a DFA to have exactly one transition from each state for each symbol in the alphabet and having that rule means that dead states must be explicit. I'm aware that some people say a DFA has at most one transition for each state/character, which does allow for an implicit dead state but I've not seen any textbook that uses this convention. $\endgroup$ – David Richerby Nov 22 '18 at 12:36
  • $\begingroup$ @DavidRicherby it depends on where you get your diagrams from, and which exact definition then use for DFA. $\endgroup$ – ratchet freak Nov 22 '18 at 12:40
  • 1
    $\begingroup$ Of course. I'm just saying that you claim that "most" diagrams use the convention you state and my experience is the exact opposite. (In fact, I've never actually seen one in something like a textbook.) $\endgroup$ – David Richerby Nov 22 '18 at 12:42
0
$\begingroup$

According to the subset construction, the state you go to from state $\{B\}$ when you read character $1$ is the set of all states that the original NFA can go to when it's in one of the states in $\{B\}$ (i.e., it's in state $B$) reads $1$. This set of states is $\emptyset$, since the NFA has no transitions from $B$ for symbol $1$.

So this actually answers both of your questions at once: it's what you do with $\emptyset$ and it's the dead state you need (you can check from the definition that $\emptyset$ really is a dead state in the DFA.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.