Thursday, April 5, 2012

Non deterministic finite automata(NFA)

Definition: An NFA is a 5-tuple or quintuple M = (Q, Σ, δ, q0, A) where
Q is non empty, finite set of states.
Σ is non empty, finite set of input alphabets.
δ is transition function which is a mapping from
Q x {Σ U ε} to subsets of 2Q. This function shows
the change of state from one state to a set of states
based on the input symbol.
q0 Q is the start state.
A Q is set of final states.

Acceptance of language

Definition: Let M = (Q, Σ, δ, q0, A) be a DFA where Q is set of finite states, Σ is set of input alphabets (from which a string can be formed), δ is transition function from Q x {ΣU} to 2Q, q0 is the start state and A is the final or accepting state. The string (also called language) w accepted by an NFA can be defined in formal notation as:

L(M) = { w | w Σ*and δ*(q0, w) = Q with atleast one
Component of Q in A}

No comments:

Post a Comment