COMP 455 Links
COMP 455 Links
Fall 2021
SYLLABUS
Class Introduction
Review
Survey
LECTURE NOTES
Alphabets and Languages
Finite Representations of Languages
Deterministic Finite Automata
Nondeterministic Finite Automata
Finite Automata and Regular Expressions
Showing Languages are Non-Regular
Minimizing Finite Automata
Context-Free Grammars
Parse Trees
Push-down Automata
Push-down Automata and Context-Free Languages
Languages that Are and Are Not Context-Free
Algorithms for Context-Free Languages
Determinism and Parsing
Turing Machines
Acceptance, Rejection, and I/O for Turing Machines
Turing Machine extensions; Nondeterminism
General Grammars
Undecidability; the Church-Turing Thesis
Universal Turing Machines
The Halting Problem
More Unsolvable Problems
Other Topics
NP Completeness
REGULAR EXPRESSIONS
Regular Expressions in Perl
The UNIX "GREP" Utility
Mastering Regular Expressions
A Tao of Regular Expressions
Wikipedia Article on Regular Expressions
FINITE AUTOMATA
Zero Counter Automaton
Parity Automaton
Universal Automaton
Java Formal Languages and Automata Package
Protein Sequence Similarity Search Programs
PRACTICE FOR EXAM 1
Practice Exam 1 (pdf)
Answers 1 (pdf)
Practice Exam 1 (latex)
Practice Exam 1 (word)
Another Practice Exam 1 (pdf)
Answers (pdf)
Practice Problems from the Text
CONTEXT-FREE LANGUAGES
Context-Free Grammar for Algol 60
Is Java Context-Free?
Python is not context free
Haskell is not context-free
Mini-Java Grammar
PRACTICE FOR EXAM 2
Practice Exam 2 (postscript)
Practice Exam 2 (latex)
Practice Exam 2 (pdf)
Practice Exam 2 (word)
Answers to Practice Exam 2 (pdf)
Another Practice Exam 2 (pdf)
Practice Problems
Solutions to Practice Problems
Practice Problems from the Text
PRACTICE FOR EXAM 3
Practice Exam 3 (pdf)
Solutions to Practice Exam 3 (pdf)
Another Practice Exam 3 (pdf)
Solutions to Another Practice Exam 3 (pdf)
Practice Problems from the Text
TURING MACHINES
A Universal Turing Machine
Bounds on the Busy Beaver Function
Proof of Uncomputability of the Busy Beaver Function
References on the Busy Beaver Function
Six State Busy Beaver Current Champion
Turing Kara
TuringKara manual in English
Kara Java archive; right click, save to disk with .jar extension, then double click.
BUSY BEAVER MACHINES
Busy Beaver machines
Simulation 1
Simulation 2
Simulation 3
Simulation a
Simulation r
PHILOSOPHICAL ISSUES
Discussion of Goedel's theorem and other incompleteness results
Discussion of unsolvability of Hilbert's tenth problem
Mathematics and the Mind
Minds, Machines, and Goedel
The Goedelian Argument
Limitations of Self Knowledge
Minds, Machines, and Mathematics
The Non-Algorithmic Character of Human Consciousness
A Puzzle
HANDOUTS
Rules of Inference for Sets
Rules of Inference for Operations on Languages
Handout 3
Handout 4
Handout 5
Handout 6
Handout 7
Handout 8
Handout 9
Handout 10
Handout 11
HOMEWORK
Homework 1
Homework 2
Homework 3
Homework 4
Homework 5
Homework 6
Homework 7
Homework 8
Homework 9
Challenge
Challenge Problem
Final Exam Schedule
Final Exam Schedule