Instructor:
Omer
Egecioglu
omer@cs.ucsb.edu
Office hrs:
T, R 2:003:00pm
HFH
2115
Teaching
Assistants:
Isaac
Mackey
isaac_mackey@cs.ucsb.edu
Office hrs:
W 1:004:00pm, Trailer 936
Mohith
Pukale
mohithpukale@cs.ucsb.edu
Office hrs:
M 2:304:30pm Trailer 936
F 2:003:00pm Trailer 936
Lecture:
TR
11:0012:15, HSSB 1173
Discussion
Sections:
08805: F 11:0011:50, PHELP 2510
08813: F 12:0012: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:003:00 or during the Friday sections.
 HW6 has been posted.
 Suggested reading: Ch. 6.16.3, 8.1.
Tuesday, November 6, 2018:
 Lecture 11
highlights: Simplification of CFGs, useless symbols, active
(productive) variables, reachable variables, bottomup and topdown
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:003:00 or during the Friday sections.
 Suggested reading: Ch. 6.16.3.
Thursday, November 1, 2018:
 Lecture 10
highlights: Discussion of the midterm exam, contextfree
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, sgrammars,
linear time parsing in sgrammars, 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, contextfree 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.12.
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, Contextfree
grammars (CFG), linear grammars, rightlinear and leftlinear grammars,
equivalence of regular languages and languages generated by
rightlinear grammars, closure of regular languages under reversal,
reversal and CFGs, equivalence of regular languages and languages
generated by leftlinear 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.13.
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.12.
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.13.
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.12.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.
