Automata theory has a lot of proofs. Sometimes I don't get how this is a proof. Take for example the equivalence of NFAs and DFAs: the proof for this statement (two-way hypothesis and conclusion) shows how to "convert an NFA to DFA" and vice versa. How can this be a proof given that we ourselves have done changes in the construction of one from the other?
Similarly, there is this pumping lemma which I understood how to apply but not well enough to prove it. I need to understand these proofs in a very detailed manner so that I can write it myself.
Also, if we are to look at Sipser's textbook, it skipped a lot of topics in automata theory, for example:
- Finite automata with output (Mealy and Moore machines).
- Greibach normal form.
- Closure properties.
- Decision algorithms for context-free languages.
- Equivalence of pushdown automata accepted by final state and accepted by empty stack.
- Equivalence of PDAs and CFGs.
- Converting regular grammars to finite automata and vice versa.
Where can I find a detailed description of the above topics with their respective proofs?