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?

  • 1
    $\begingroup$ Perhaps Sipser's textbook is not the correct one for you. $\endgroup$ – Yuval Filmus Apr 14 '15 at 6:00
  • $\begingroup$ Can you refer any kind of text that deals with the above mentioned concerns or topics or both in a very detailed manner? $\endgroup$ – user4275686 Apr 14 '15 at 6:54
  • 1
    $\begingroup$ This is too broad. If you have questions about specific, feel free to ask about those. As for a book, I do not have it at hand but, iirc, Hopcroft/Ullman is a comprehensive classic. Given the breadth of your "gaps", you may have to pick up more than one book, though. I recommend skimming the resp. tables of contents in the formal languages (or automata theory) section in your library. $\endgroup$ – Raphael Apr 14 '15 at 9:51
  • $\begingroup$ How to prove pumping lemma for regular languages? $\endgroup$ – user4275686 May 4 '15 at 13:08

Browse other questions tagged or ask your own question.