CS516

Theory of Computation and Formal Languages

School of Electrical Engineering and Computer Science
Oregon State University
Corvallis, OR 97331
Instructor: Prasad Tadepalli
Office: 3069 Kelley Engineering Center
Instr. Office Hrs: T 10:00-11:00,F 11:00 - 12:00; Other times by appointment
Class Time: MWF 10:00-10:50 AM, Location: Owen 101
email: tadepall AT eecs DOT orst DOT edu
This web page: http://www.EECS.ORST.EDU/~tadepall/cs516/08

Text:

Learning Objectives of the Course:

  1. Design deterministic and non-deterministic finite state automata, and regular expressions; prove their correctness, and convert from one to the other.
  2. Design grammars for context-free languages, push down automata, convert one to the other.
  3. Describe the properties of regular and context-free languages and use them to decide if a language is regular or context-free.
  4. Design Turing Machines for problems. Show the equivalence between different versions of Turing Machines.
  5. Prove decidability and undecidability of languages.

Course contents:

Grades:

Your grades will be based on the homeworks, in-class quizzes, one midterm, and the final. The current grades are here . I'll use the following weights.

To do well in this course:

  1. Don't miss the class.
  2. Read the text book regularly.
  3. Do the homework completely and on time.
  4. Study the solutions for problems answered in the book.
  5. Get help from me when needed.

Collaborations:

You are encouraged to study together and discuss general strategies for problems with one another. However, if you collaborate with someone on the homework, you should state that clearly on your homework. Everyone is responsible for their answers even if they work with someone else. Mindless copying of someone else's answers will be considered as dishonesty and could result in an F grade. You should also not use any web sources for answering the homework questions unless explicitly instructed.

Prasad Tadepalli,
tadepall AT cs DOT orst DOT edu