Search code examples
automatafinite-automata

Nondeterministic finite acceptors basic question

While studying automata class lecture, I have a really basic question in nfa.

Q0-a>Q1-lambda>Q2

If graph looks like that,(I can’t post images yet, FYI Q0-a>Q1 means there is edge (q0,q1) with labeled with a) Can i say that delta(q0,a)=q2 ? I think my question is little bit silly but I wanna know the answer!

Solution

  • Yes, if the graph looks like

    (q0) --a--> (q1) --e--> (q2)

    Then it is fair to say that

    delta(q0, a) = (q1)

    Now, this is not to say that (q1) is the only state reachable from (q0) by consuming one a. Instead, what is typically done is another function delta* is defined, maybe from pairs of sets of states and symbols to other sets of states, so that

    delta*({(q0)}, a) = {(q1), (q2)}

    If you want to be sure, specify the domain and codomain of delta to eliminate any confusion.