cs 138 Automata and Formal Languages
Summer B 2019
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:3001:50pm
 Instructor Office Hours: Wednesday 4:006:00pm
 Instructor's Office: Harold Frank Hall 1119
 Teaching Assistant: Shane Masuda (masuda@ucsb.edu)
 Discussion Schedule and Room:
Wednesday 02:0003:20pm, Phelps 2510
 TA Office: Trailer 936 Room 104
 TA Office Hours: Thursday 2:004: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
←
 2pages 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
lowresolution phonecamera 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]
Contextfree languages and grammars.
Parsing and ambiguity.
 Week 5: [Sections 6.1, 6.2, 7.1, 7.2, 7.3]
Simplification of contextfree grammars.
Chomsky and Greibach normal forms.
Nondeterministic and deterministic pushdown 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
contextfree grammars; properties of contextfree 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ç
