**Unit 1: Review: Theory of Computation**
*In the first part of this unit, the student will learn about
representing information, the concept of languages, the notion of
programs, and the concept of non-determinism. Then, we will get an
overview of the mathematical systems of finite-state transducers and
grammatical characterizations of the languages that finite-memory
programs accept. The last part of the unit covers the mathematical
systems of Turing transducers. Also, we will discuss the relationship
between determinism and non-determinism in Turing transducers.*

**Unit 1 Time Advisory**

This unit will take approximately 27 hours to complete.

☐ Subunit 1.1: 7 hours

☐ Subunit 1.2: 7 hours

☐ Subunit 1.3: 4 hours

☐ Subunit 1.4: 8 hours

☐ Unit 1 Assessment: 1 hour

**Unit1 Learning Outcomes**

Upon successful completion of this unit, the student will be able to:

- Define alphabets and strings.
- Explain the meaning of string orderings.
- Define representation.
- Explain the principles of abstracted finite-memory programs.
- Define a finite state automaton and regular language.
- Explain recursion.
- Define context free language.
- Describe Turing transducers.
- Explain the difference between non-determinism and determinism.
- List the characteristics of universal Turing transducers.

**1.1 General Concepts**
- **Reading: Ohio State University: Eitan Gurari’s An Introduction to
the Theory of Computation: “Chapter 1: General Concepts”**
Link: Ohio State University: Eitan Gurari’s *An Introduction to the
Theory of Computation:* “Chapter 1: General
Concepts”
(HTML)

Instructions: Read the introductory webpage titled “General
Concepts." Then, click on the hyperlinks for each section 1.1-1.5,
and read each webpage in its entirety. From this reading, you will
learn about strings and the role that strings have in representing
information. This reading relates the concept of languages to the
notion of strings and introduces grammars for characterizing
languages. Also, this text deals with the notion of programs and
the concept of non-determinism in programs. This reading covers
subunits 1.1.1 through 1.1.3 of this course.

Terms of Use: Please respect the copyright and terms of use
displayed
here.

**1.1.1 Alphabets, Strings, and Representations**
**1.1.2 Formal Languages and Grammars**
**1.1.3 Programs**
**1.2 Finite-Memory Programs**
- **Reading: Ohio State University: Eitan Gurari’s An Introduction to
the Theory of Computation: “Chapter 2: Finite-Memory Programs”**
Link: Ohio State University: Eitan Gurari’s *An Introduction to the
Theory of Computation:* “Chapter 2: Finite-Memory
Programs”
(HTML)

Instructions: Please read the “Finite-Memory Programs” webpage, and
then click on each hyperlink for sections 2.1-2.6. Read each
section in its entirety to learn about the mathematical systems of
finite-state transducers. This reading also provides grammatical
characterizations for the languages that finite-memory programs
accept. This reading covers subunits 1.2.1 through 1.2.3 of this
course.

Terms of Use: Please respect the copyright and terms of use
displayed
here.

**1.2.1 Motivation**
**1.2.2 Finite-State Transducers**
**1.2.3 Finite-State Automata and Regular Languages**
**1.3 Recursive Finite-Domain Programs**
- **Reading: Ohio State University: Eitan Gurari’s An Introduction to
the Theory of Computation: “Chapter 3: Recursive Finite-Domain
Programs”**
Link: Ohio State University: Eitan Gurari’s *An Introduction to the
Theory of Computation:* “Chapter 3: Recursive Finite-Domain
Programs”
(HTML)

Instructions: Please read the introductory webpage titled
“Recursive Finite-Domain Programs.” Then, click on each hyperlink
for sections 3.1-3.6, and read each section in its entirety to learn
about the notion of recursion in programs and recursive
finite-domain programs, which are characterized by finite-state
transducers. A grammatical characterization for recursive
finite-domain programs is provided in section 3.3. This reading
covers subunits 1.3.1 through 1.3.3 of this course.

Terms of Use: Please respect the copyright and terms of use
displayed
here.

**1.3.1 Recursion**
**1.3.2 Pushdown Transducers**
**1.3.3 Context-Free Languages**
**1.4 General Programs**
- **Reading: Ohio State University: Eitan Gurari’s An Introduction to
the Theory of Computation: “Chapter 4: General Programs”**
Link: Ohio State University: Eitan Gurari’s *An Introduction to the
Theory of Computation:* “Chapter 4: General
Programs”
(HTML)

Instructions: Please read the introductory page titled “General
Programs.” Then, click on the hyperlinks for sections 4.1-4.7, and
read each webpage in its entirety. Section 4.1 is about the
mathematical systems of Turing transducers as a generalization to
pushdown transducers. In section 4.2, you will learn about the
relationship between the general class of programs and Turing
transducers. Section 4.3 considers the relationship between
determinism and non-determinism in Turing transducers. Section 4.4
shows the existence of a Turing transducer, called a universal
Turing transducer, which can be programmed to compute any computable
function. This reading covers the topics outlined in subunits 1.4.1
through 1.4.4 of this course.

Terms of Use: Please respect the copyright and terms of use
displayed
here.

**1.4.1 Turing Transducers**
**1.4.2 Programs and Turing Transducers**
**1.4.3 Non-Determinism versus Determinism**
**1.4.4 Universal Turing Transducers**
- **Assessment: The Saylor Foundation's "CS411: Unit 1 Quiz"**
The Saylor Foundation does not yet have materials for this portion
of the course. If you are interested in contributing your content to
fill this gap or aware of a resource that could be used here, please
submit it here.

```
[Submit Materials](/contribute/)
```