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?


closed as too broad by Luke Mathieson, D.W., hengxin, David Richerby, Raphael Apr 14 '15 at 9:48

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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.