computation-theoryfinite-automatanfanon-deterministic

NFA that does not accept strings ending "101"


What is the NFA that does not accept strings ending "101"?


Solution

  • There can be "n" number of NFA possible for the finite automata.In non-deterministic finite automata on any input symbol trasitions to zero or more states is possible.To accept the string that does not ending with 101 one of the NFA is:

    Transitions are:
    ∆(q0,0)={q0}
    ∆(q0,1)={q0,q1}
    

    Here, intial state q0 on input symbol 0 can remain in the same state or can go to the next state q1 and on the input symbol 1 go to next state q1. q0 can be the final state.

    ∆(q1,0)={q2}
    ∆(q1,1)={q1}
    

    here,q1 on input symbol 0 go to state q2 and on inputt symbol 1 remains in the same state.q1 can also be the final state.

    ∆(q2,0)={q2}
    ∆(q2,1)={q3}
    

    Here, q2 on input symbol 0 remains in the same state and on the input symbol 1 goes to next state q3. q2 can also be final state.

    ∆{q3,0)={q2}
    ∆(q3,1)={q2,q1}
    

    Here, q3 on symbol 0 goes to the state q2 and on input symbol 1 can go to q1 or q2. The state q3 can not be the final state as it accepts the string ending with 101.

    Other NFA's can also be done for the same question which can also be correct.

    enter image description here