5 Course Materials Outline

5.1 Textbook Topics Outline

The following is a list of those chapters and sections which will be covered in the course. For each chapter or section, a symbol is given which indicates the nature of coverage in the course. The meaning of these symbols is provided in the table below.

• In general, omitted items will not be covered. However, the possibility that some covered material may appear in an omitted chapter or section remains. In all cases, the lectures and course notes should be taken to be the definitive statement for the course material.

1

Introduction to the Theory of Computation

1.1

Mathematical Preliminaries and Notation ✙

1.2

Three Basic Concepts ✔

1.3

Some Applications ✥

2

Finite Automata

2.1

Deterministic Finite Acceptors ✔

2.2

Nondeterministic Finite Acceptors ✔

2.3

Equivalence of Deterministic and Nondeterministic Finite Acceptors ✔

2.4

Reduction of Number of States in Finite Automata ✘

3

Regular Languages and Regular Grammars

3.1

Regular Expressions ✔

3.2

Connection Between Regular Languages and Regular Expressions ✔

3.3

Regular Grammars ✔

4

Properties of Regular Languages

4.1

Closure Properties of Regular Languages ✔

4.2

Elementary Questions about Regular Languages ✔

4.3

Identifying Nonregular Languages ✔

5

Context-Free Languages

5.1

Context-Free Grammars ✔

5.2

Parsing and Ambiguity ✔

5.3

Context-Free Grammars and Programming Languages ✔

6

Simplification of Context-Free Languages and Normal Forms

6.1

Methods for Transforming Grammars ✔

6.2

Two Important Normal Forms ✔

6.3

A Membership Algorithm for Context-Free Grammars ✥

7

Pushdown Automata

7.1

Nondeterministic Pushdown Automata ✔

7.2

Pushdown Automata and Context-Free Languages ✥

7.3

Deterministic Pushdown Automata and Deterministic Context-Free Languages ✥

7.4

Grammars for Deterministic Context-Free Languages ✘

8

Properties of Context-Free Languages

8.1

Two Pumping Lemmas ✥

8.2

Closure Properties and Decision Algorithms for Context-Free Languages ✥

9

Turing Machines

9.1

The Standard Turing Machine ✔

9.2

Combining Turing Machines for Complicated Tasks ✥

9.3

Turing’s Thesis ✔

10

Other Models of Turing Machines

10.1

Minor Variations on the Turing Machine Theme ✥

10.2

Turing Machines with More Complex Storage ✥

10.3

Nondeterministic Turing Machines ✔

10.4

A Universal Turing Machine ✔

10.5

Linear Bounded Automata ✘

11

A Hierarchy of Formal Languages and Automata

11.1

Recursive and Recursively Enumerable Languages ✔

11.2

Unrestricted Grammars ✥

11.3

Context-Sensitive Grammars and Languages ✥

11.4

The Chomsky Hierarchy ✔

12

Limits of Algorithmic Computation

12.1

Some Problems That Cannot Be Solved by Turing Machines ✔

12.2

Undecidable Problems for Recursively Enumerable Languages ✔

12.3

The Post Correspondence Problems ✥

12.4

Undecidable Problems for Context-Free Languages ✥

12.5

A Question of Efficiency ✥

13

Other Models of Computation

13.1

Recursive Functions ✘

13.2

Post Systems ✘

13.3

Rewriting Systems ✘

14

An Overview of Computational Complexity

14.1

Efficiency of Computation ✔

14.2

Turing Machine Models and Complexity ✔

14.3

Language Families and Complexity Classes ✔

14.4

The Complexity Classes P and NP ✔

14.5

Some NP Problems ✔

14.6

Polynomial-Time Reduction ✔

14.7

NP-Completeness and an Open Question ✔

5.2 Other Topics to be Covered

There are a number of topics which are not covered in the textbook but are related to the course material and are important for computer scientists to know. central to the course. These topics cover in particular, but not exclusively, important applications of the theory. They will be covered in the lectures and slides, and are listed below.

XFA1 Extended regular expressions in programming and systems:

The regular expressions which are studied in the course are are proper subset of the “regexps” which are used in many programming environments. A brief comparison of the features of each will be made.

XFA2 Tools for parsing and using regular expressions:

Regular languages and expressions are widely used, particular in the description and construction of scanners for programming languages. A brief overview of tools which have been developed for this purpose, such as Lex and Flex will be given. Unfortunately, due to a lack of any prerequisite for a knowledge of C and systems programming, no obligatory assignments using these tools will be possible.

XFA3 Modelling in computer systems using finite automata:

The textbook considers finite automata only as acceptors of languages. However, such automata are widely used in more general ways to model aspects of computer systems. A brief overview of such modelling techniques will be given.

XCF1 Faithfulness to semantics – weak vs. strong representation:

In many cases, the processing of languages involves assigning a meaning (semantics) to a string, and this requires that the underlying grammar be faithful to that semantics. An overview of what this entails will be given.

XCF2 Overcoming the limits of context-free languages:

Although context-free languages are widely used in the modelling of both computer and natural languages, it is impossible to recapture such languages precisely using the context-free formalism. The ways in which this limitation is overcome will be discussed briefly.

XCF3 Parsing and understanding natural language:

The representation and processing of natural (i.e., human) languages poses problems not found with computer languages. A brief overview of how these issues are addressed will be given.

XCF4 Tools for parsing and using context-free languages:

As context-free grammars are widely used for representing computer languages, tools for building parsers have been developed, Yacc and Bison being amongst the best known. A brief overview of what these tools can do will be given. Unfortunately, due to a lack of any prerequisite for a knowledge of C and systems programming, no obligatory assignments using these tools will be possible.

XCT1 The programming-language alternative to Turing Machines:

While the classical model of Turing is still the most widely used representation for computability, it is not the most intuitive. For many purposes, a simple model based upon imperative while programs is more natural. This model will be presented briefly.

XCT2 Rice’s Theorem for recursive languages:

There is a simple and very general characterization of undecidable properties of languages which is unfortunately not covered in the textbook. Due to its simplicity and importance, it will be developed in the course notes and lectures.

5.3 Online Materials

There web site for the course is located at

The following materials may be found on these pages.

1. This syllabus, in both PDF and HTML.
2. The lecture slides for the course.
3. Descriptions of the obligatory exercises.
4. Miscellaneous links to computation-related things.
5. Some official documents required by the Department of Computing Science.