Search code examples
computer-sciencecomputation-theoryfinite-automatadfanfa

Conversion of NFA having a missing transition for any input character on initial state to DFA

I was practicing NFA (Non-Deterministic-Finite-Automata) designing and converting them to DFA.

Then suddenly I got a doubt, as all the examples I have seen for conversion had NFA's initial state with all the transition, that is for every input character.

The tabular method of conversion requires to put initial state in the table, and that becomes the initial state of DFA as well.

But what when there is not all transtion present for every input character on the Initial state? Consider the example below....

Example: If we want to create NFA for 1^n0^m, where both n and m is greater than zero.

So I created something like this for a NFA: enter image description here

Now if we make a transition table for this... It would be something like this:

enter image description here

And since we consider the initial state as it is when deriving the DFA transition table: enter image description here

But from NDFA's table q0 has no transition defined for input 0. In such situation how one should proceed...?

I got stuck, as the initial state itself isn't complete.

Also I am really confused when designing the NFA, as NFA aren't deterministic, so any clutter other than the language string can also get accpeted. While desinging a DFA, states and transtion can be removed by the process of elimination or accpetance.

**By posting this question here, I don't hope to achieve answer to this specific question. ** What I am looking for any specific set of rules when designing NFA and converting them to DFA, along with corner cases as well, such as above. From my understanding I am specifically looking for NFA, not for epsilon-NFA where null moves can be made.

Any reference or in-depth study material will be greatly appreciated.

Solution

  • So after going through a few more similar questions here relating NFA to DFA conversion and picking details about them. I got a better understanding.

    As none of those questions was tailored to my understanding, here I am putting the answer that I only got because of those questions posted.

    The first question was "Is there any specific set of rules for designing NFA?". The answer is No, apart from the very few basic rules we have, there is no specific way to go about it. As long as we are not aiming to achieve Minimum NFA, there could be infinite NFA accepting the same language, with redundant states and transitions obviously.

    "But from NDFA's table q0 has no transition defined for input 0. In such a situation how one should proceed...?" If any such case arrives, it means that the DFA will transition to a dead state. (I went to the whole theory about how we need to find a state in the power set of Q, to find the DFA).

    Here's the solution for anyone who stumbles upon the same confusion(don't know if helps, but anyway)

    NFA's δ
    enter image description here

    So here's how the procedure goes.

    1. First write down the initial state transitions as it is:
      enter image description here

    2. If there exists any collective transition to multiple states for any specific input from the initial state- in this case to {q0,q1} on input 1, then that collection of states should be considered as a single state and would be part of the DFA.
      DFA's δ in building
      enter image description here

    3. To expand or define the transtion of {q0, q1} we need to find all states in power set of {Q} which transitate on each input character from this {q0, q1}, where Q is the set of NFA's states.
      The simplest way to do this is to take the union of transitions on states for {q0, q1} from NFA's delta.
      So for input 0, as highlighted q0 leads to ⲫ, and q1 leads to {q1, q2}, and their union would be {q1, q2}.
      enter image description here

      Hence in DFA {q0, q1} will lead to {q1, q2} for input 0.
      DFA's δ in building
      enter image description here

      In the same manner for input 1, q0 leads to {q0, q1} and q1 leads to ⲫ, and their union would be {q0, q1}.
      enter image description here

      In this manner, our DFA can be completed...
      DFA's δ in building
      enter image description here

    4. Lastly we just need to keep expanding any newly introduced states in a similar manner, until all the states in the transition table are expanded.
      So for our current state of DFA {q1, q2} hasn't been defined:

      DFA's δ in building
      enter image description here

      Let's complete this.
      For input 0 in NFA's delta
      q1->{q1, q}
      q2-> q2
      union = {q1, q2}

      enter image description here

      For input 1 in NFA's
      q-1-> ⲫ
      q2->ⲫ
      union = {ⲫ]

      enter image description here

      Since there is no longer any collective state which is not expanded, this is our final DFA. enter image description here

      And here is the Diagram for the Same:

      enter image description here

    PS: I am no painter.