Posted on December 1, 2009 by Chad Salinas

b/c they come up all the time:

Deduction Theorem: Δ |- (φ ⇒ ψ) if and only if

Δ∪{φ} |- ψ.

Substitution Theorem: Δ |- (φ ⇔ ψ) and Δ |- χ, then it

is the case that Δ |- χφ←ψ.

ChainingTheorem: IfΔ|-(φ⇒ψ)andΔ|-(ψ⇒χ), then Δ |- (φ ⇒ χ).

Filed under: Uncategorized | Tagged: Deduction Theorem Subsitution Theorem Chaining Theorem | Leave a comment »

Posted on November 8, 2008 by Chad Salinas

Posted on April 25, 2008 by Chad Salinas

Posted on April 25, 2008 by Chad Salinas

Posted on April 25, 2008 by Chad Salinas

Review the following:

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

Filed under: Automata & Complexity Theory | Tagged: Add new tag | Leave a comment »

Posted on July 31, 2007 by Chad Salinas

Posted on July 30, 2007 by Chad Salinas

Theorem: NFA, 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 transitions.

Filed under: Automata & Complexity Theory | Leave a comment »