I am working with converting an NFA to a DFA and came across an odd set notation issue that I don't know how to answer.

Say I have the following NFA and assume the starting state to be zero: NFA attached here

So if I let q0 = A, q1 = B, q2 = C then B is my only accepted state.

Looking at all 3 states with transitions 0 and 1 I find transition 0 to be the following

A -> {A,B}

B -> {C}

C -> {emptyset}

With Transition 1 I get the following:

A -> {B}

B -> {C}

C -> {C}

so in my DFA A takes me to state {AB} an accepting state with 1 or {B} also an accepting state with 0 and I need to carry on to minimize the states.

Eventually I end up with the following with transition 0:

{ABC} -> {A,B,C,NULL}.

Can I translate this into $A$ or $B$ or $C$ or $\emptyset$?

  • $\begingroup$ Some additional context would be helpful. $\endgroup$ Feb 16, 2017 at 18:01
  • $\begingroup$ I added the actual problem in addition to the support provided by John's edits. @MichaelBurr I can attach my steps and a picture of where I am currently stuck as well if that helps. $\endgroup$
    – Callat
    Feb 16, 2017 at 19:13

1 Answer 1


I believe you must have encountered a state which has no transition specified for a particular input symbol. As for your question yes you can take the union(OR) of Sets with NULL $\space\emptyset$ which is nothing but the non-empty set itself. For example : $$\{q1 , q2 ,q0\}\cup\{\emptyset\} = \{q1 , q2 ,q0\}$$

  • $\begingroup$ Hmmmm.... That's what I was afraid of. Because if I can't specify all the transitions I don't think that it is convertable. I solved it under the assumption of what you posted but I doubt my answer is correct. Double and triple checking my method showed me that I assumed what you posted was correct without actually being sure. So I came here to ask . Thank you $\endgroup$
    – Callat
    Feb 16, 2017 at 19:16
  • $\begingroup$ what if it was an intersection? Would the result be the empty set? $\endgroup$
    – Callat
    Feb 16, 2017 at 21:01
  • 1
    $\begingroup$ @Kaz Rodgers yes it will be an empty set in case of intersection $\endgroup$ Feb 17, 2017 at 3:52
  • 1
    $\begingroup$ Since your answer made sense to the OP, but makes no sense to me, I ask you to retag this. This is certainly not a set theory problem. $\endgroup$
    – Asaf Karagila
    Feb 17, 2017 at 6:59
  • $\begingroup$ It's been done. Thanks for letting me know the appropriate tag $\endgroup$
    – Callat
    Feb 17, 2017 at 14:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .