المحاضرة الرابعة -احتسابية1

• Finite State Automata with ? moves:
If the definition of a NFSA is altered , so that moves from one state to another can be accomplished without any input we say that the automaton has ?-moves .More formally , a NFSA M=(Q , ? , t ,S,F) has ?-moves if t, instead of being a function Q x ??2Q , is defined as a function
Q x ( ? U{?}) ? 2Q .
t-(Q, ?)=R(Q)
t-(Q, ?)=R(t(R(Q), ?))


• Convert NFSA with empty move into NFSA without empty move.

If there is NFSA with empty move M = ( Q, ?, q0 , t , F ) then there is FSA without empty move M- = (Q- , ?, q0 , t- , F- )
Define t : Q×( ? ? {?} ) ? Q
By
t (K,?)=R(K) or ?-closure(K)
t (K,a)=R(t(R(K),a))
The set of final states F- is F ?{q}if R(q) ?F

Example:
Convert the NFSA with empty move into without empty move.

• Finite State Automata with ? moves:
If the definition of a NFSA is altered , so that moves from one state to another can be accomplished without any input we say that the automaton has ?-moves .More formally , a NFSA M=(Q , ? , t ,S,F) has ?-moves if t, instead of being a function Q x ??2Q , is defined as a function
Q x ( ? U{?}) ? 2Q .
t-(Q, ?)=R(Q)
t-(Q, ?)=R(t(R(Q), ?))


• Convert NFSA with empty move into NFSA without empty move.

If there is NFSA with empty move M = ( Q, ?, q0 , t , F ) then there is FSA without empty move M- = (Q- , ?, q0 , t- , F- )
Define t : Q×( ? ? {?} ) ? Q
By
t (K,?)=R(K) or ?-closure(K)
t (K,a)=R(t(R(K),a))
The set of final states F- is F ?{q}if R(q) ?F

Example:
Convert the NFSA with empty move into without empty move.