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