Welcome!

Welcome to the support website for Computational Models as taught at Luther College. The text for the course is Peter Linz’s Formal Languages and Automata, 5th edition. Do not buy the newer edition as it is formatted differently than the 5th edition.

Here you will find some supplementary materials to accompany Linz’s text. For the most part what you will find here are descriptions for programming problems. However, in the first chapter there are some introductory topics that are perhaps covered a little too fast for our course. We’ll spend some time studying predicate logic and set theory before we launch into the later chapters of Linz’s text.

Contents

• 1. Introduction to the Theory of Computation
  • 1.1. Propositional Logic
    • 1.1.1. Propositional Logic Operators
    • 1.1.2. Proof by Truth-Tables
    • 1.1.3. Practice
    • 1.1.4. Equivalence and Inference Rules
    • 1.1.5. Proof by Derivation
    • 1.1.6. Proof by Contradiction
    • 1.1.7. Other Proof techniques
    • 1.1.8. Exercises
  • 1.2. Sets
    • 1.2.1. Exercises
    • 1.2.2. Infinite Sets
    • 1.2.3. Exercises
  • 1.3. Functions and Relations
  • 1.4. Graphs and Trees
  • 1.5. Three Basic Concepts
• 2. Finite Automata
  • 2.1. The Ordered Collections
  • 2.2. The State Class
  • 2.3. JPython Programming Language Example
  • 2.4. The StreamReader Class
  • 2.5. An NFA Example
  • 2.6. A Scangen Input File
  • 2.7. NFA to DFA Conversion
    • 2.7.1. The Function
    • 2.7.2. The NFA to DFA Algorithm
    • 2.7.3. Example Calculator Language
  • 2.8. DFA Minimization
    • 2.8.1. The Finer Function
    • 2.8.2. Example Minimal DFA
  • 2.9. Regular Expressions To NFAs
    • 2.9.1. The Algorithm
    • 2.9.2. The Operate Function
    • 2.9.3. Reading the Input
  • 2.10. Programming Exercises
• 3. Regular Languages and Regular Grammars
• 4. Properties of Regular Languages
• 5. Context-Free Languages
• 6. Simplification of Context-Free Grammars and Normal Forms
• 7. Pushdown Automata
  • 7.1. Nondeterminstic Pushdown Automata
  • 7.2. LL(1) Grammars
  • 7.3. LALR(1) Grammars
  • 7.4. Building the LR0 Machine
    • 7.4.1. The Completion Function
    • 7.4.2. The Successor Function
  • 7.5. The LR0State Class and its Components
  • 7.6. Computing Lookahead Sets
  • 7.7. Running the LALR(1) Machine
  • 7.8. Exercises