COMP 455 Links

COMP 455 Links

Spring 2013

COURSE EVALUATION FORM


SYLLABUS

REGULAR EXPRESSIONS
Regular Expressions in Perl

Perl 6 Regular Expressions

The UNIX "GREP" Utility

Using Regular Expressions

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)

Practice Exam 1 (latex)

Practice Exam 1 (word)

Another Practice Exam 1 (pdf)

Practice Problems from the Text

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)

Another Practice Exam 2 (pdf)

Practice Problems

Solutions to Practice Problems

Practice Problems from the Text

PRACTICE FOR EXAM 3
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.

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

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