Non-Deterministic Finite Automaton (NFA) A non-deterministic finite automaton (NFA)is a mathematical model that consists of: -S-a set of states ->-a set of input symbols (alphabet) move-a transition function move to map state-symbol pairs to sets of states. So -a start(initial)state F-a set of accepting states(final states) 8-transitions are allowed in NFAs.In other words,we can move from one state to another one without consuming any symbol. A NFA accepts a string x,if and only if there is a path from the starting state to one of accepting states such that edge labels along this path spell out x. CS308 Compiler Theory 10Non-Deterministic Finite Automaton (NFA) • A non-deterministic finite automaton (NFA) is a mathematical model that consists of: that consists of: – S - a set of states – Σ - a set of in p y (p ) ut s ymbols (al phabet ) – move – a transition function move to map state-symbol pairs to sets of states. – s0 - a start (initial) state – F – a set of accepting states (final states) a set of accepting states (final states) • ε - transitions are allowed in NFAs In other words we can move from transitions are allowed in NFAs. In other words, we can move from one state to another one without consuming any symbol. • A NFA accepts a string x if and only if there is a path from the starting A NFA accepts a string x, if and only if there is a path from the starting state to one of accepting states such that edge labels along this path spell out x. CS308 Compiler Theory 10