Part I. AUTOMATA

Table of Contents

1. Automata and Formal Languages
1.1. 1.1 Languages and grammars
1.1.1. 1.1.1 Operations on languages
1.1.2. 1.1.2 Specifying languages
1.1.3. 1.1.3 Chomsky hierarchy of grammars and languages
1.1.4. 1.1.4 Extended grammars
1.1.5. 1.1.5 Closure properties in the Chomsky-classes
1.2. 1.2 Finite automata and regular languages
1.2.1. 1.2.1 Transforming nondeterministic finite automata
1.2.2. 1.2.2 Equivalence of deterministic finite automata
1.2.3. 1.2.3 Equivalence of finite automata and regular languages.
1.2.4. 1.2.4 Finite automata with special moves
1.2.5. 1.2.5 Minimization of finite automata
1.2.6. 1.2.6 Pumping lemma for regular languages
1.2.7. 1.2.7 Regular expressions
1.3. 1.3 Pushdown automata and context-free languages
1.3.1. 1.3.1 Pushdown automata
1.3.2. 1.3.2 Context-free languages
1.3.3. 1.3.3 Pumping lemma for context-free languages
1.3.4. 1.3.4 Normal forms of the context-free languages
2. Compilers
2.1. 2.1 The structure of compilers
2.2. 2.2 Lexical analysis
2.2.1. 2.2.1 The automaton of the scanner
2.2.2. 2.2.2 Special problems
2.3. 2.3 Syntactic analysis
2.3.1. 2.3.1 parser
2.3.2. 2.3.2 parsing
3. Compression and Decompression
3.1. 3.1 Facts from information theory
3.1.1. 3.1.1 The Discrete Memoryless Source
3.1.2. 3.1.2 Prefix codes
3.1.3. 3.1.3 Kraft's inequality and noiseless coding theorem
3.1.4. 3.1.4 Shannon-Fano-Elias-codes
3.1.5. 3.1.5 The Huffman coding algorithm
3.2. 3.2 Arithmetic coding and modelling
3.2.1. 3.2.1 Arithmetic coding
3.2.2. 3.2.2 Modelling
3.3. 3.3 Ziv-Lempel-coding
3.3.1. 3.3.1 LZ77
3.3.2. 3.3.2 LZ78
3.4. 3.4 The Burrows-Wheeler-transform
3.5. 3.5 Image compression
3.5.1. 3.5.1 Representation of data
3.5.2. 3.5.2 The discrete cosine transform
3.5.3. 3.5.3 Quantisation
3.5.4. 3.5.4 Coding
4. Reliable Computation
4.1. 4.1 Probability theory
4.1.1. 4.1.1 Terminology
4.1.2. 4.1.2 The law of large numbers (with “large deviations”)
4.2. 4.2 Logic circuits
4.2.1. 4.2.1 Boolean functions and expressions
4.2.2. 4.2.2 Circuits
4.2.3. 4.2.3 Fast addition by a Boolean circuit
4.3. 4.3 Expensive fault-tolerance in Boolean circuits
4.4. 4.4 Safeguarding intermediate results
4.4.1. 4.4.1 Cables
4.4.2. 4.4.2 Compressors
4.4.3. 4.4.3 Propagating safety
4.4.4. 4.4.4 Endgame
4.4.5. 4.4.5 The construction of compressors
4.5. 4.5 The reliable storage problem
4.5.1. 4.5.1 Clocked circuits
4.5.2. 4.5.2 Storage
4.5.3. 4.5.3 Error-correcting codes
4.5.4. 4.5.4 Refreshers