CODEWITHSUNDEEP
stringbinaryfinite-automata
Venom2901
Venom2901

Reputation: 19

How to construct a NFA which accepts all binary strings which start with a 0?

Just want some help or hint in how to construct an MFA which starts with 0

Upvotes: 0

Views: 4383

Answers (2)

Devindi Peiris
Devindi Peiris

Reputation: 24

L={Set of strings starts with "0"} ={0,00,01,000,001,010,011,...}

First, we start with the initial state (q0). Then if we get "0" as the input it should direct to the final state (q1, since we check that "0" is the first). Here we are not concerned about what happens if it gets "1" as the input. Because here we are designing an NFA not a DFA. After getting "0" as the first input there can be "0"/"1" inputs later. So, we represent them on the q1 state. NFA for the question above

Upvotes: 1

Patrick87
Patrick87

Reputation: 28292

A nondetermistic finite automaton (NFA) for all binary strings (Alphabet = {0, 1}) which begin with zero (0) can be constructed as follows.

First, we know the NFA needs an initial state. All NFAs need an initial state. Call this q0.

When we initially enter state q0, we have not yet seen the required 0; the empty string does not start with 0. Therefore, the initial state q0 is not accepting. So far, our NFA has no accepting states. That means it doesn't accept anything yet. Our language has strings in it though, so we know that any NFA must have more than just the initial, non-accepting state q0. Call the other state we know we need q1.

We have introduced q1 because we need an accepting state. Starting from q0, if we see the symbol 0, we have seen a string (indeed, the shortest string) in the target language. The transition from q0 on symbol 0 must terminate in some accepting state. We might as well terminate in q1; so, we add the transition f(q0, 0) = q1.

Our DFA now accepts the finite language consisting of the length-one string 0; L(M) = {0}. We are not accepting anything else so far. However, the language we want to accept includes longer strings. Therefore, we need some more stuff in our NFA. We know that what we've added so far is logically mandatory and any correct NFA for the language will do essentially what we have done so far (modulo empty, epsilon- or lambda- transitions which are never necessary).

In particular, we want to accept more strings that start with 0. All strings that start with 0 will take the transition we added from q0 to q1. So, in state q1, we need to accept basically anything we see from that point on. If we see a 0 next, we need to land in an accepting state; and if we see a 1 next, we need to land in an accepting state - and so on, forever. Because at this point we don't need to distinguish between any kinds of strings, we can simply add transitions from q1 back to itself on either 0 or 1.

Our NFA so far looks a bit like this:

               +----+
               |    | 0, 1
               V    |
----->q0----->q1----+
          0

You should be able to convince yourself that this NFA accepts the intended language, because:

  • the shortest string it accepts is 0
  • if it accepts string x, it accepts string x0 and x1
  • all strings beginning with 0 can be constructed using the above rules
  • no string failing to begin with 0 can be constructed using the above rules

Upvotes: 1

Related Questions