Pumping Lemma

April 25, 2008

What is the importance of the Pumping Lemma?

1 Comment | Automata & Complexity Theory | Tagged: , | Permalink
Posted by Chad Salinas

Automata & Complexity Theory

April 25, 2008

Review the following:

  • DFA
  • NFA
  • Regular Expressions
  • Inductive proofs
  • Constructive proofs
  • CFGs
  • Turing Machines
  • Undecidability
  • Computational Complexity

 

Leave a Comment » | Automata & Complexity Theory | Tagged: | Permalink
Posted by Chad Salinas

NFA vs. DFA

July 30, 2007

Theorem:  \forall NFA, \exists a DFA that recognizes the same language.

 Of course iff proofs require bi-direction, even when one direction is trivial.

Has it really been that long ago???  Just give me a state and a symbol so I can union it with the existing states…

 Don’t forget about \epsilon transitions.

Leave a Comment » | Automata & Complexity Theory | Permalink
Posted by Chad Salinas