UCSB
COMPUTER SCIENCE 138: 
Automata and Formal Languages
Fall 2018

                      Syllabus Assignments                                      
Instructor: 
Omer Egecioglu
omer@cs.ucsb.edu
Office hrs:
T, R 2:00-3:00pm
HFH 2115

Teaching Assistants:
Isaac Mackey
isaac_mackey@cs.ucsb.edu

Office hrs:
W 1:00-4:00pm, Trailer 936

Mohith Pukale
mohithpukale@cs.ucsb.edu

Office hrs:
M 2:30-4:30pm Trailer 936
F 2:00-3:00pm Trailer 936

Lecture: 
TR 11:00-12:15, HSSB 1173

Discussion Sections: 
08805: F 11:00-11:50, PHELP 2510
08813: F 12:00-12:50, PHELP 2510

Required Textbook:

Peter Linz, An Introduction to Formal Languages and Automata, Sixth Edition, Jones & Bartlett, 2017.
 Thursday, November 8, 2018:
  • Lecture 12 highlights: Simplification of CFGs,  null and unit productions, nullable variables, eliminating null productions, an intermediate normal form, the Chomsky Normal Form (CNF).
  • You can pick up your graded exam during office hours T,R 2:00-3:00 or during the Friday sections.
  • HW6 has been posted.
  • Suggested reading: Ch. 6.1-6.3, 8.1.
Tuesday, November 6, 2018:
  • Lecture 11 highlights: Simplification of CFGs, useless symbols, active (productive) variables, reachable variables, bottom-up and top-down algorithms, the emptiness problem for CFGs, reduced grammars, a substitution rule,  null and unit productions, eliminating unit productions.
  • You can pick up your graded exam during office hours T,R 2:00-3:00 or during the Friday sections.
  • Suggested reading: Ch. 6.1-6.3.
Thursday, November 1, 2018:
  • Lecture 10 highlights: Discussion of the midterm exam, context-free grammars and languages, derivations, derivation (parse) trees, partial derivation trees, yield of a derivation tree, traversals, leftmost and rightmost derivations, exhaustive search parsing, null and unit productions, problems with exhaustive search parsing, s-grammars, linear time parsing in s-grammars, ambiguity of CFGs, inherent ambiguity of CFLs.
  • HW5  has been posted.
  • Suggested reading: Ch. 5, 6.1.
Tuesday, October 30, 2018:
  • Midterm exam.
  • The exam has been graded. You will get it back during discussion on Friday. The average grade was 57/100. The histogram of the grades is here: 
Thursday, October 25, 2018:
  • Lecture 9 highlights: Standard representation of regular languages, algorithmic nature of conversions between standard representation, decision problems, decision algorithms, decision algorithms for regular languages,  direct construction for the intersection of regular languages, closure under quotients, existential issues for quotient by arbitrary languages revisited, context-free grammars and languages, derivations, examples.
  • The midterm exam is on Tuesday, October 30. It is closed book and closed notes. You will not need a bluebook. Be sure to bring your ID.
Tuesday, October 23, 2018:
  • Lecture 8 highlights: More on the pumping lemma for regular languages, examples of nonregular languages, using closure properties for showing nonregularity, homomorphisms, closure of regular languages under homomorphic images and inverse homomorphic images, algorithms for regular languages, algorithm to check if the language accepted by a DFA is infinite.
  • Suggested reading: 5.1-2.
Thursday, October 18, 2018:
  • Lecture 7 highlights: Closure properties of regular languages, closure under quotients, existential issues for quotient by arbitrary languages, long walks in DFA, the pigeonhole principle, the Pumping Lemma (PL)  for regular languages, the adversary argument in the PL, examples of nonregular languages, using closure properties to show nonregularity.
  • Suggested reading: 3.3, Ch. 4.
Tuesday, October 16, 2018:
  • Lecture 6 highlights: An example DFA that remembers parities, Context-free grammars (CFG), linear grammars, right-linear and left-linear grammars, equivalence of  regular languages and languages generated by right-linear grammars, closure of regular languages under reversal, reversal and CFGs, equivalence of regular languages and languages generated by left-linear grammars, regular grammars, closure of regular languages under complement, union, concatenation, star closure and intersection.
  • You can pick up your old HWs from me during office hours.
  • Suggested reading: 3.3, 4.1-3.
Thursday, October 11, 2018:
  • Lecture 5 highlights: Regular expressions and the languages they denote, every regular expression denotes a regular language. Examples, every regular language is denoted by a regular expression, a dynamic progrramming formulation, constructiong regular expressions for some languages.
  • Here is an example dynamic programming computation to determine the regular expression denoting the language accepted by a given DFA.
  • HW3 has been posted.
  • Suggested reading: Chapter 3, 4.1-2.
Tuesday, October 9, 2018:
  • Lecture 4 highlights: Short review of DFA, walks and words, regular languages, nondeterminism, NFA, λ-transitions, three ways in which NFA are different from DFA, acceptance in NFA, the existential nature of acceptance, eliminating λ-transitions, when λ is in the language, the moving token analogy, keeping track of the status of the token, subset construction and simulating an NFA by a DFA, final states of the simulator DFA, regular expressions (Regex), recursive definition, hierarch of operators *, ., +, regular expressions and the languages they denote.
  • Suggested reading: 2.3, 3.1-3.
Thursday, October 4, 2018:
  • Lecture 3 highlights: More shorthand expressions, quotients of languages, examples, finite state machines, transducers and acceptors, binary adder, binary to quaternary converter, Deterministic Finite Automata (DFA), what determinism means, extending the transition function to all words over the alphabet, walks and words, acceptance, the language accepted by a DFA, definition of regular languages, examples, trap states, DFA for  {a,b}-words without aa as subword (NOAA), closure of regular languages under complementation.
  • HW2 has been posted.
  • Suggested reading: Ch 2 (excluding 2.4), 3.1.
Tuesday, October 2, 2018:
  • Lecture 2 highlights: Equations involving words, words of length n, repeated concatenation, Kleene (star) closure, positive closure, generating words in canonical order, palindromes, shorthand expressions, grammars, variables, terminals, productions, start variable, sentential forms, derivations, language generated by a grammar, examples, even length palindromes over {a,b}, palindromes over {a,b}, {a,b}-words without aa as subword (NOAA), {a,b}- words and lattice paths, grammar for the language EQUAL.
  • Suggested reading: Ch1, 2.1-2.3.
Friday, September 28, 2018:
  • The registrar's office has decided that the sections for this course will be held in room PHELP 2510. So starting next week, both sections will meet at PHELPS 2510. Sorry for this confusion.
Thursday, September 27, 2018:
  • Lecture 1 highlights: Course outline, mechanics of the course, languages and machine models, a problem with dominoes, alphabets, letters, words, strings, length, the null word λ, the number of occurences of a letter in a word, concatenation, the set of all words over an alphabet, languages, concatenation of languages, repeated concatenation, prefixes, suffixes, equality of words, dictionary order and canonical/proper order.
  • Suggested reading: Ch. 1, 2.1.
  • HW1 has been posted.
Preliminary Announcements: 
  • Please read the syllabus for this course. It has important information about this class, exam and final exam dates, grading policy, code of conduct,  etc. You can access it through the Syllabus link above.
  • Students are responsible for monitoring changes to this page and the course's other web pages. 
  • For email communications, make sure to include the word "CS138" in your subject line.
  • We are going to use Piazza for discussions, Q&A about this class. Please sign up here: Piazza. You are encouraged to take part in the discussions.
  • There are two copies of the textbook available for 2 hour checkout at the Davidson library.
  • The first homework (HW1) will be posted on Thursday, September 27. Homeworks should be turned in to the CS138 Homework box in room 2108 in HFH by the due date/time. Homeworks and their posting/due dates can be accessed through the Assignments link above.