Search code examples
regular-languagenfa

NFA to accept set of all binary strings with 2, 5, 8, 11,... number of 1s

How to construct a NFA which accepts set of all strings w such that n1(w) mod 3 > 1, where n1(w) is the number of 1s in w over the alphabet = {0,1}?

So, basically a NFA which accepts the set of all strings with 2, 5, 8,... number of 1s.

I guess the regular expression for the language would be (0*10*10*)(0*10*10*10*)*

I can create a NFA for the above regular exp, but I'm not sure if this can be reduced further or if it's even correct in the first place. I'm new to regular languages, DFA, NFA stuff. Please help me!

Solution

  • Let me propose this NFA, over alphabet {0,1}:

    Q = {A, B, C}
q0 = {A}
F = {C}
d = {(A,0,A)
     (A,1,B)
     (B,0,B)
     (B,1,C)
     (C,0,C)
     (C,1,A)}

    Please check whether it satisfies the requirement.