This course provides an introduction to models of computation and
computability. In particular, we will ask the question,

List of topics include:

- Determinstic finite automata (DFA), Non-deterministic finite automata (NFA), and their equivalence.
- Regular expressions, equivalence between regular expressions and finite automata, properties of regular languages, and the pumping lemma.
- Context-free grammars (CFG), properties of context-free languages, and pushdown automata.
- Turing machines (TM), variants of TMs, and Church-Turing Thesis.
- Undecidable problems, diagonalization, and Rice's Theorem.
- Unrecognizable problems.

**Instructor**

Seung Geol Choi (Office hours: Stop in anytime, or email for an appointment.
Research day is Thursday)

**Links**

- Course homepage: http://www.usna.edu/Users/cs/choi/courses/si340/f13/index.html
- Calendar: http://www.usna.edu/Users/cs/choi/courses/si340/f13/si340.html

**Learning Objectives**

- Understand the various models of computation, from both the formal language and the corresponding machine model perspective;
- Apply the mathematical methods that let us describe computation and language in order to understand formal algorithms.

**Program Outcomes** - Goals for the whole major
to which this course contributes

- (PO a) An ability to apply knowledge of computing and mathematics appropriate to the discipline
- (CS-j) An ability to apply mathematical foundations, algorithmic principles, and computer science theory in the modeling and design of computer-based systems in a way that demonstrates comprehension of the tradeoffs involved in design choices

**Textbook**

We will use Introduction
to the Theory of Computation, Third Edition by Michael Sipser, Course
Technology.

**Extra Instruction**

You are strongly encouraged to come in for extra instruction (EI) when you are
having trouble. You may just stop by your instructor's office, or make an
appointment in advance to ensure availability. If you miss class, get the notes
from the section leader or other classmate.

**Grading**

The break-down on your final grades will be:

- 20%: Homeworks
- 6%: Quizzes
- 34%: Exams 1 and 2
- 40%: Final Exam

Mid-semester grades for the 6-Week and 12-Week marking periods will be calculated by giving 80% weight to exam/quiz grades and 20% weight to homework grades.

The final exam will be cumulative.

**Honor**

You are required to abide by the ** USNA and department honor policies at all
times **, including, but not limited to: The
Honor Concept of the Brigade of Midshipmen, and the Policies
Concerning Graded Academic Work.

You may discuss homework problems with your classmates freely, but must **
write your own solution, and list the names of all people that you collaborated
with**. If you use a source other than the textbook in doing your homework,
explain the material from the source in your own words and acknowledge the
source. Collaboration without acknowledgment is considered cheating. ** In
any case, you are not allowed to look at written solutions of any other student
(even if you worked on solving the homework together) or of any other external
sources.**

**Section Leader**

The duties of the section leader include:

- calling the section to attention at the beginning and end of class reporting absences to the instructor
- contacting the department office (3-6800, Room 346) if the instructor is more than 10 minutes late for class
- directing the class in productive work if the instructor is absent

**Abscences**

You are responsible for obtaining any material missed due to an absence. You
must ensure your work is submitted on time regardless of other commitments,
i.e. duty, sick call, MO, etc. Should emergencies arise, it is your
responsibility to coordinate in advance with the instructor (emergency leave,
hospitalization, SIR, etc.).

There will be no make-up for missed quizzes. You can miss at most two quizzes
with little harm, but you must accept the consequence missing more than two.

**Classroom Decorum**

Beverages are permitted in classrooms and labs provided they
are in closed containers. No food is permitted in classrooms
or labs.
**You are not allowed to use a laptop or a smartphone during the lecture.**