Notes on automata theory

Remarks from Motwani, Hopcroft & Ullman : Introduction to Automata Theory, Languages and Computation (during 45min reading) :
Chapter 2 : Finite Automata
- Give an example of practical communication/transaction protocol which can only be analyzed via automata model
- Examples of structural patterns which require formal verification of correctness ?
- Complexity bound for automata which require formal verification?
(even in the case of 2 simple, say 4-state automata, their single interconnection yields a product of automata resulting in 16-state automata )

- Optimal representation of DFA ? (space-efficient Transition Tables). Alternative methods of representation ?
- Algorithm-efficient representations ? (ex. finding all loops in automation by observing transition table -> can we speedup the algoritm by using structure other than table)

A NFA models the ability of input to "guess" the right state. Actually this can be seen as increasing complexity in order to simplify the description. The automata can reduce complexity of the problem by increasing the description. However, there are problems that cannot be treated in this manner.

A NFA is more descriptive than DFA, while there should be a 1-1 mapping NFA <-> DFA (Using a Tompson's algorithm , we can efficiently construct the DFA corresponding to NFA). Still, a NFA of size N corresponds to a DFA of size N+K . How do we prove the 1-1 mapping then ?

- [Offtopic] -> how can we efficiently create a program for automata generation via feeding it with a list of input examples and accept/reject results for each example ?