Nondeterminstic Finite Automata

NFA are a generalized from of deterministic finite automata where each state can have zero, one, or many transition/exit arrows.

NFA computation

If a state has multiple transitions, then compute in parallel, prune the computations that do not fall in an accepting state by end of string or end in a state without a transition for the current input symbol. If any one of the banches does end at a accepting state then the string is recognized. If an epsilon is encountered then branch each of them for the next input symbol...

NFA formal def.

Transition function changes from f(state, alphbet) -> state to f(state, alphbet or empty) -> subset of P(states)

NFA to DFA

Refer to the page for the formal way of doing it. Follow the 'reader as automaton' strategy, keep track of the states hit, the set of states unioned become a state in the DFA with the union of the transition function becoming the transition function of the DFA.

Generalized NFA

transition arrows are now regular expressions, recursive process to convert GNFA of the special form to a regex

Pumping lemma

All regular expressions have the property s.t. they can be deconstructed into x(y^i)z ... there are many conditions, but this lemma is used with proof by contradiction to determine if a langauge is regular