cs 138 Automata and Formal Languages

cs 138 Automata and Formal Languages

Department of Computer Science
University of California Santa Barbara
http://koclab.cs.ucsb.edu/teaching/cs138

Course Information

  • Instructor: Professor Çetin Kaya Koç         → Koç is pronounced as "Coach"  

  • Class Room: Phelps 2510
  • Class Schedule: Tuesday, Wednesday, Thursday 12:30-01:50pm

  • Instructor Office Hours: Wednesday 4:00-6:00pm
  • Instructor's Office: Harold Frank Hall 1119

  • Teaching Assistant: Shane Masuda (masuda@ucsb.edu)

  • Discussion Schedule and Room:
    Wednesday 02:00-03:20pm, Phelps 2510

  • TA Office: Trailer 936 Room 104
  • TA Office Hours: Thursday 2:00-4:00pm

  • Please join the Piazza page for class discussions.   ←
  • Check the class website, the Piazza page, and/or your email once a day.

  • Slides and other course information are in the folder docx   ←
  • Homework assignments are exams are in the folder hwex   ←
  • The grades: cs138.htm   (The Code is your PERM number mod 98729)

Exams and Homework Assignments

  • The Midterm Exam will be in class during class time on Tuesday, Aug 27   ←
  • The Final Exam will be in class during class time on Thursday, Sep 12   ←
  • 2-pages of notes (both sides) are allowed during the Exams.
  • No makeup exam can be given under any circumstances.

  • We will have 6 Homework Assignments
  • Homework Assignments are due 5pm on Fridays
  • Either, upload an electronic copy to a Dropbox folder (to be provided), or deliver a paper copy to the HW Box in HFH 2108. Electronic copy of your homework or lab report can be in Text, PDF or MS Word. You could also scan/pdf your handwritten work, however, do not submit small and/or low-resolution phone-camera images.
  • Homework Assignment 1: hw1.html - due 5pm Friday, Aug 9

  • Homework Assignment 2: hw2.html - due 5pm Friday, Aug 16

  • Homework Assignment 3: hw3.html - due 5pm Friday, Aug 23

  • Homework Assignment 4: hw4.html - due 5pm Friday, Aug 30

  • Homework Assignment 5: hw5.html - due 5pm Friday, Sep 6

  • Homework Assignment 6: hw6.html - due 5pm Friday, Sep 13
    Dropbox Link for hw6

Weekly Course Plan

  • Week 1a: [Sections 1.1, 1.2, 1.3] Mathematical preliminaries. Languages, grammars, and automata.
  • Week 1b: [Appendix A] Finite state transducers, Mealy and Moore machines, equivalence, minimization.
  • Week 2: [Sections 2.1, 2.2, 2.3, 2.4] Deterministic and nondeterministic finite accepters. Equivalence of dfa and nfa. Reduction of states.
  • Week 3: [Sections 3.1, 3.2, 3.3] Regular expressions. Connections between regular expressions and regular languages. Regular grammars.
    [Sections 4.1, 4.2, 4.3] Closure properties of regular languages. Elementary questions about regular languages. Identifying regular languages.
  • Week 4: [Sections 5.1, 5.2] Context-free languages and grammars. Parsing and ambiguity.
  • Week 5: [Sections 6.1, 6.2, 7.1, 7.2, 7.3] Simplification of context-free grammars. Chomsky and Greibach normal forms. Nondeterministic and deterministic push-down automata.
  • Week 6: [Sections 9.1, 9.2,, 12.1] Turing machines. Limits of algorithmic computation.

Textbook

Grading Rules

  • Homework assignments: 40 %
  • Midterm exam: 30 %
  • Final exam: 30 %
  • Late HW: Every late day subtracts 20 % from the homework grade.

Course (Catalog) Description

Formal languages; finite automata and regular expressions; properties of regular languages; pushdown automata and context-free grammars; properties of context-free languages; introduction to computability and unsolvability. Introduction to Turing machines and computational complexity.

Prerequisites

CS 40; open to computer science and computer engineering majors only.

Academic Integrity at UCSB   ←

Dr. Çetin Kaya Koç