Computation Theory

Formal languages and automata

Tentative topics

• mod1: Regular languages and finite automata
• mod2: Context-free languages and pushdown automata
• mod3: Turing languages and machines

Referenced textbooks

• ict: Introduction to computer theory, 2e
• ialc: Introduction to Automata Theory, Languages, and Computation
• Introduction to the Theory of Computation, 3rd edition
  • 18.404/6.5400: Introduction to the Theory of Computation
  • 18.404j: Theory of Computation
• Introduction to Theoretical Computer Science
  • CS-121 / CSCI-E121: Introduction to Theoretical Computer Science
• Computational Complexity: A Modern Approach
• Theory of Computation

Referenced classes

• CS 154: Introduction to the Theory of Computation
  • Ullman
  • Reingold
    • github
• ECS 120: Theory of Computation
• CMSC 28000: Introduction to Formal Languages
• CPT S 317: AUTOMATA AND FORMAL LANGUAGES
• CS 390: Introduction to computation theory
• CS 341 Automata Theory
• CS 162 - Formal Languages and Automata Theory
• CS 4810 Introduction to the Theory of Computing
• 15-453 Formal Languages, Automata, and Computation

---

• CS 344: Design and Analysis of Computer Algorithms sp21

Online resources

• regular expression
  • regular expression 101
  • Regular Expressions Gym
• automata
  • FSM Simulator
  • FSM simulator
    • noam
  • Automaton Simulator
  • Automata simulator online
  • Automata and Regular language in Sage
  • Automata simulator in Java
    • dk.brics.automaton
  • Automata Playground
• CFGs: context-free grammars
  • CFG Testing suite
    • source
  • The Context Free Grammar Checker
  • CFG Developer
• lexer and parser generators
  • ANTLR
    • src