0

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

Community
  • 1
Callat
  • 111
  • 5
  • Some additional context would be helpful. – Michael Burr Feb 16 '17 at 18:01
  • 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. – Callat Feb 16 '17 at 19:13

1 Answers1

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\}$$

Michael Burr
  • 32,867
Shubham Singh rawat
  • 226
  • 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 – Callat Feb 16 '17 at 19:16
  • what if it was an intersection? Would the result be the empty set? – Callat Feb 16 '17 at 21:01
  • 1
    @Kaz Rodgers yes it will be an empty set in case of intersection – Shubham Singh rawat Feb 17 '17 at 03:52
  • 1
    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. – Asaf Karagila Feb 17 '17 at 06:59
  • It's been done. Thanks for letting me know the appropriate tag – Callat Feb 17 '17 at 14:02