Instructor:
Omer
Egecioglu
omer@cs.ucsb.edu,
Teaching
Assistants:
Mohammad Javad Amiri
amiri@cs.ucsb.edu
John RettererMoore
retterermoore@cs.ucsb.edu
Lecture:
MW 9:30  10:45 am, Phelps 1160
Section (Fridays, Girvetz 1116):
9:00
 9:50 am (EnrlCd 08573 )
10:00  10:50 am (EnrlCd 08581 )
Required
Textbook:
Peter Linz, An Introduction to Formal Languages and Automata, Fifth Edition, Jones & Bartlett, 2011


Friday, May 1, 2015:
 Solutions to HW4 have been posted..
Wednesday, April 29, 2015:
 The midterm exam is on Monday, May 4, 2015.
 There will be a review session conducted by TA John on Sunday, May 3, 2015, 3:005:00 pm in Phelps 3526.
 You can check the piazza for solutions to the practice exam that John may post.
 Lecture 9. Topics covered: Contextfree
grammars and contextfree languages, sentential forms, direct
derivations, derivations, Aproductions, nullproductions,
unitproductions, examples of contextfree languages and grammars,
grammars for the languages NOAA, PALIN, DYCK and EQUAL, derivation as
graph reachability, brute force parsing in 2w rounds.
 Reading assignment: 5.1  5.3.
Tuesday, April 28, 2015:
 The midterm exam is on Monday, May 4, 2015. Here is a practice test from an earlier CS 138: practice test
Monday, April 27, 2015:
 Lecture 9. Topics covered: The
pigeonhole principle, the pumping lemm (PL) for regular languages, how
to prove languages nonregular, the adversary model, using closure
properties, nonregularity of a number of languages considered in class.
 Reading assignment: 5.1  5.2
Wednesday, April 22, 2015:
 My office hour for today (Wednesday, April 22) has been moved to 12:0012:50.
 I will have additional office hours tomorrow (Thursday,April 23) 10:0011:30 am.
 Lecture 8. Topics covered: Standard
models for regular languages, more on linear grammars and regular
languages, homomorphisms, inverse homomorphisms, the closure of regular
languages under homomorphisms and inverse homomorphisms, decision
algorithms for regular languages, membership, emptiness, finiteness,
containment, equality, an example of a (provably) nonregular language.
Tuesday, April 21, 2015:
 HW4 has been posted. It is due on
Wednesday, April 29 at 4:00pm. Homeworks and their posting/due dates can
be accesses through Homework Assignments link above.
 My office hour for tomorrow (Wednesday, April 22) has been moved to 12:0012:50.
 You can get back your graded HW2 (and HW1 if you have not got it back yet) in the discussion session on Friday.
Monday, April 20, 2015:
 Lecture 7. Topics covered: NFA
with wordtransitions, left linear, right linear, regular, linear
grammars, reversals, equivalence of the right (left) linear
grammars and regular languages, closure of regular
languages under union,
concatenation, starclosure, complementation, reversal and
intersection, De Morgan's rule, direct construction for the
intersection, right quotients of languages, regularity of the right
quotients of regular languages by arbitrary languages, existential
nature of this proof.
 Reading assignment: 3.3, 4.1  4.3
Wednesday, April 15, 2015:
 Lecture 6. Topics covered: Regular
expressions, conventions for regular expressions, proof that the
languages denoted by regular expressions are regular languages, an
algorithm for a regular expression for the language accepted by a DFA.
As a result, L is regular iff L is accepted by a DFA iff L is accepted
by an NFA iff L=L(r) for a regular expression r.
 Here is an example (left incomplete in class) of the
algorithm to find a regular expression denoting the language accepted
by a DFA: example.jpg.
Tuesday, April 14, 2015:
 Solutions to HW1 have been posted.
 HW3 has been posted. It is due on
Wednesday, April 22 at 4:00pm. Homeworks and their posting/due dates can
be accesses through Homework Assignments link above.
Monday, April 13, 2015:
 HW2
is due on Wednesday by 4:00 pm. Note that
there are no late homeworks allowed in this course.
 Make use of Piazza for discussions, Q&A about this class. This is a very useful resource.
 Lecture 5. Topics covered: Review
of DFA/NFA, keeping track of nondeterminism, the moving token analogy,
equivalent automata, keeping track of subsets of states in NFA,
equivalence of NFA and DFA (simulating NFA by DFA), the special role
for the null word, the closure of regular languages under union,
concatenation and starclosure.
 Reading assignment: Skip section 2.4, read 3.1, 3.2.
Wednesday, April 8, 2015:
 Lecture 4. Topics covered: Elements of graph theory, vertices,
edges, walks, paths, simple paths, finite state machines, transition
diagrams, 5tuple definition, Deterministic Finite Automata (DFA), the
language accepted by a DFA,regular languages, complementation,
Nondeterministic Finite Automata (NFA), the criterion for acceptance
by an NFA, examples.
 Reading assignment: Ch 2.
Tuesday, April 7, 2015:
 Starting next week, TA John's office hours will be 2:003:50 pm on
Tuesdays in TRAILER 936 (instead of what was given in the
original syllabus.)
 HW2 has been posted. It is due on
Wednesday, April 15 at 4:00pm. Homeworks and their posting/due dates can
be accesses through Homework Assignments link above.
Monday, April 6, 2015:
 HW1
is due on Wednesday by 4:00 pm. Make sure you make use of office hours
to ask questions, especially to make sure that your arguments are
convincing. Do not leave the homework to the last minute: note that
there are no late homeworks allowed in this course.
 You should make use of Piazza for discussions, Q&A about this class. This is a very useful resource.
 Lecture 3. Topics covered: A
bit of a review, succint representation of languages, lattice paths and
the 2letter alphabet, grammars, terminals, productions, derivations,
language generated by a grammar, equivalent grammars, palindromes, the
DYCK language, examples of grammars, state diagrams, transitions,
transducers, example of a binary to quaternary converter.
 Reading assignment: Ch 2.
Thursday, April 2, 2015:
 Make
sure that you include the words "CS138" in your subject line if you
need to ask something by email. This is to make sure your message
actually gets read.
 Tomorrow's discussion sections will be held as scheduled.
Wednesday, April 1, 2015:
 Note that TA John's office hours will be 4:006:00 pm on
Tuesdays in TRAILER 936 (instead of 4:406:30 pm as given in the
syllabus handed out the first day of classes).
 Lecture 2. Topics covered: Concatenation
of languages, starclosure and positive closure, prefixes, suffixes;
proper prefixes, proper suffixes, algebralike notation for powers,
disjoint union and concatenation. Lexicographic (dictionary, or lex)
order, canonical (proper) order, generating words in lex order,
generating words in canonical order, proving identities involving
languages.
Tuesday, March 31, 2015:
 HW1 has been posted. It is due on
Wednesday, April 8 at 4:00pm. Homeworks and their posting/due dates can
be accesses through Homework Assignments link above.
Monday, March 30, 2015:
 The staff and the mechanics of this course.
 Lecture
1. Topics covered: Principles of computers, immediate applications
of formal languages and automata theory: digital design, programming
languages, compilers.Topics to be covered in the course. A problem with
dominos called PCP. Introduction to sets, Boolean operations, finite
& infinite sets, power set, complements, De Morgan's laws, etc.,
partitions, definition of alphabets, words, languages, concatenation,
length, the null word. Notation, similarity/differences with
multiplication, associativity, noncommutativity.
 Reading assignment: pp. 127.
Preliminary Announcements:
 Please read the syllabus for this course. It has
important information about this class, such as office hours, exam
dates, etc. You can access is through the Syllabus link above.
 A copy of the textbook has been placed in the RBS for 2hour checkout.
 Students are responsible for monitoring changes to this page and the course's
other web pages.
 For email communications, make sure ti include the word "CS138" in your subject line.
 We are going to use Piazza for discussions, Q&A about this class. You are encouraged to take part in this.
 The
first homework (HW1) will be posted on Tuesday, March 31. Homeworks
should be turned in at the CS138 HW Box in
room 2108, Harold Frank Hall by the due date/time. HW1 is due on
Wednesday, April 8 at 4:00pm. Homeworks and their posting/due dates can
be accesses through Homework Assignments link above.
