Languages and Machines
These notes provided an integrated treatment of many topics in mathematics that are important in computing science.
An introduction explores logic, set theory and the techniques of proof construction. A chapter on strings and languages sets the scene for the remaining chapters. Machines that process formal languages are discussed in a fair amount of depth – finite state machines and Turing machines. The final two chapters are concerned with cryptography and error-correcting codes.
[Please note that all links are to Adobe .pdf documents. They will open in a separate browser window.]
- Introduction and Contents
- CHAP01 Logic
- CHAP02 Languages
- CHAP03 Sets, Functions and Relations
- CHAP04 Introduction to FSAs
- CHAP05 Reduction of FSAs
- CHAP06 Non-Deterministic FSAs
- CHAP07 FSAs and Regular Languages
- CHAP08 Turing Machines
- CHAP09 Extended Turing Machines
- CHAP10 Busy Beaver
- CHAP11 Arithmetic Modulo m
- CHAP12 Cryptography
- CHAP13 Polynomial Codes
- APPENDIX A: Mathematical terms
- APPENDIX B: Patterns of Proof
- APPENDIX C: Summary