we define an NFA
- a 5-tuple (Q, Σ, δ, s, F), where
- a set of states Q is a finite set
- an alphabet Σ is a finite, non-empty set
- a start state s in Q
- a set of final states F contained in Q
- a transition function d is a function Q * (∪{Σ})→2Q
- go through the formal definition
Definition
- Let M = (Q, Σ, δ, s, F) be a non-deterministic finite automaton, and (q0, w0) and (q1, w1) be 2 configurations of M.
- We say (q0, w0) yields (q1, w1) in 1 step, which can denoted by (q0, w0) -/M (q1, w1), if q1 ε δ (q0, a,), and w0=a w1, for some a ∈ δ∪{ε}.
Definition
- Assume M = (Q, Σ, δ, s, F) be an NFA, and (q0, w0) and (q1, w1) be 2 configurations of M. (q0, w0) yields (q1, w1) in zero step or more, which can be denoted by (q0, w0) -/*M (q1, w1), if
- q0= q1 and w0 = w1, or
- (q0, w0) -/M (q2, w2) and (q2, w2) -/*M (q1, w1) for some q2 and w2.
Definition
- Let M = (Q, Σ, δ, s, F) be the NFA, and ω ∈ * Σ. We say M accepts ω if (s, ω) -/*M (f, ε), when f ε F. Else, we say M rejects ω.
Email based Automata assignment help - homework help
The study of automata is an important area of theory of computation. Students feel trouble in solving automata questions. We at www.expertsmind.com offers Automata assignment help - Automata homework help and online tutoring with best qualified and experienced computer science tutor's help. We cover all topics including Define an NFA in assignment help - homework help service. Get solved problems in automata theory with step by step answers anytime from expert tutors at expertsmind.