##
Theoretical Computer Science - Bridging Course

Material from Past Bridging Courses

Fabian Kuhn

# Past exercise sheets

#### Winter Term 2016/2017

Topic(s) |
Exercise |
Sample Solution |
||||

Mathematical Preliminaries | Exercise 01 | Solution 01 | ||||

DFA, NFA, Regular Languages | Exercise 02 | Solution 02 | ||||

Regular expressions Non-regular languages |
Exercise 03 | Solution 03 | ||||

Context Free Grammars I Context Free Grammars II |
Exercise 04 | Solution 04 | ||||

Pushdown Automata Pumping Lemma for Context Free Grammars |
Exercise 05 | Solution 05 | ||||

Turing Machines I Turing Machines II |
Exercise 06 | Solution 06 | ||||

Decidability and decidable languages Decidability, mathematical backgrounds on cardinality Decidability and the halting problems |
Exercise 07 | Solution 07 | ||||

Complexity I Complexity II |
Exercise 08 | Solution 08 | ||||

Complexity III | Exercise 09 | Solution 09 | ||||

Propositional Logic. Deduction/ Contraposition/Contradiction Theorems and Derivations | Exercise 10 | Solution 10 | ||||

Propositional Logic. Derivations, Soundness and Completeness of calculi Propositional Logic. Refutation-completeness and Resolution | Exercise 11 | Solution 11 | ||||

First Order Logic. Derivations First Order Logic. Satisfaction |
Exercise 12 | Solution 12 | ||||