CS 311 Computational Structures

Credit Hours:

4

Course Coordinator:

David Ely

Course Description:

Introduces the foundations of computing. Regular languages and finite automata. Context-free languages and pushdown automata. Turing machines and equivalent models of computation. Computability. Introduction to complexity. An appropriate programming language is used for programming experiments.

Prerequisites:

CS 251

Goals:

The main goal of the course is that students obtain those skills in the theoretical foundations of computing that are used in the study and practice of computer science. A second goal is that students become familiar with Prolog as an experimental tool for testing properties of computational structures.

Upon the successful completion of this class, students will be able to:

1. Find regular grammars and context-free grammars for simple languages whose strings are described by given properties.
2. Apply algorithms to: transform regular expressions to NFAs, NFAs to DFAs, and DFAs to minimum-state DFAs; construct regular expressions from NFAs or DFAs; and transform between regular grammars and NFAs.
3. Apply algorithms to transform: between PDAs that accept by final state and those that accept by empty stack; and between context-free grammars and PDAs that accept by empty stack.
4. Describe LL(k) grammars; perform factorization if possible to reduce the size of k; and write recursive descent procedures and parse tables for simple LL(1) grammars.
5. Transform grammars by removing all left recursion and by removing all possible productions that have the empty string on the right side.
6. Apply pumping lemmas to prove that some simple languages are not regular or not context-free.
7. State the Church-Turing Thesis and solve simple problems with each of the following models of computation: Turing machines (single-tape and multi-tape); while-loop programs; partial recursive functions; Markov algorithms; Post algorithms; and Post systems.
8. Describe the concepts of unsolvable and partially solvable; state the halting problem and prove that it is unsolvable and partially solvable; and use diagonalization to prove that the set of total computable functions cannot be enumerated.
9. Describe the hierarchy of languages and give examples of languages at each level that do not belong in a lower level.
10. Describe the complexity classes P, NP, and PSPACE.

Textbooks:

Introduction to the Theory of Computation, Michael Sipser, 2012

Major Topics:

• Regular languages and regular expressions, deterministic and nondeterministic automata, constructing efficient automata, topics (regular grammars, pumping lemma).
• Context-free languages and pushdown automata, topics (transforming grammars, pumping lemma).
• Turing machines, Church-Turing thesis, equivalent models of computation.
• Computability: undecidable problems, hierarchy of languages, complexity (P, NP, PSPACE, completeness).

Oral and Written Communications:

Every student is required to submit 3 written reports (not including exams, tests, quizzes, or commented programs) of typically 10 pages in a lab notebook.

Theoretical Content:

The entire course is theoretical material (algebraic and computational structures).

Problem Analysis:

The course is devoted to problem solving techniques of algebra and computability. The exercises and tests require problem analysis to find out which tools of algebra and computability are needed to solve a problem.

Solution Design:

The course is devoted to problem solving techniques. The exercises and tests require students to solve problems by applying the tools of algebra and computability.