3
$\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?

Improve this question
$\endgroup$
2
  • $\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.
    Commented Nov 22, 2018 at 5:22
  • $\begingroup$ Sorry, I am using Subset Construction Method. $\endgroup$
    – NBray
    Commented Nov 22, 2018 at 5:26

2 Answers 2

Reset to default
3
$\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.

Improve this answer
$\endgroup$
4
  • 2
    $\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
    Commented Nov 22, 2018 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
    Commented Nov 22, 2018 at 12:40
  • 2
    $\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
    Commented Nov 22, 2018 at 12:42
  • $\begingroup$ @DavidRicherby, I've seen it, but clearly labelled as a simplification. $\endgroup$
    – vonbrand
    Commented Feb 23, 2020 at 19:48
1
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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