compilers

Formal Language and Automata Theory

Automata and Languages

1. Regular Languages

1. Finite Automata
   1. Formal Definition
   2. Examples
   3. Formal Definition of Computation
   4. Designing Finite Automaton
   5. The regular operations
2. Nondeterminism
   1. Formal Definition
   2. Equivalance of NFAs and DFAs
   3. Closure under regular operations
3. Regular Expressions
   1. Formal Definition
   2. Equivalence with finite automata
4. Nonregular Languages
   1. The pumping lemma for regular languages

2. Context Free Languages

1. Context-Free Grammars
   1. Formal Definition of context-free grammar
   2. Examples
   3. Designing context-free grammars
   4. Ambiguity
   5. Chomsky Normal Form
2. Pushdown Automata
   1. Formal Definition
   2. Examples of pushdown automata
   3. Equivalence with context-free grammars
3. Non-Context-Free Languages
   1. The pumping lemma for context-free languages
4. Deterministic Context-Free Languages
   1. Properties of DCFLs
   2. Deterministic context-free grammars
   3. Relationship of DPDAs and DCFGs
   4. Parsing and LR(k) Grammars

Computability Theory

1. Turing Machines
   1. Formal Definition
   2. Examples
2. Variants of Turing Machines
   1. Multitape Turing Machines
   2. Nondeterministic Turing Machines
   3. Enumerators
   4. Equivalence with other models
3. The definition of Algorithm
   1. Hilbert’s Problem
   2. Terminology for describing Turing Machines
4. Decidable Languages
   1. Decidable problems concerning regular languages
   2. Decidable problemes concering context-free languages
5. Undecidability
   1. The diagnolization method
   2. An undecidable language
   3. A Turing unrecognizable language
6. Undecidable Problems from Language Theory
   1. Reductions via computation histories
7. A simple undecidable problem
8. Mapping reducibility
   1. Computable reducibility
   2. Formal definition fo mapping reducibility

All Resources

1. Kozen Computability

2. Sipser PDF

3. Turing Machines Problems

4. CFL Problems

5. PDA Example

6. CFL Examples

7. Midsem/CT Solutions

8. Pumping Lemma Problems

9. DFA/NFA Problems

10. Tutorials

11. Slides