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


Thursday, May 28, 2015:
 The reading material from the text for the rest of the
quarter is as follows: 9.19.3, 10.110.4,11.1, 12.1.
Additional
sections/topics will be discussed as time permits. Please do this
reading  the examples in the book covered in the sections indicated
will help you with the last homework assignment (HW8).
 HW8 has been posted. It is due on Friday, June 5 at 4:00pm. Homeworks and their posting/due dates can
be accesses through Homework Assignments link above.
Wednesday, May 27, 2015:
 Lecture 15. Topics covered: Constructing a CFG for the language accepted by a PDA, deterministic CFLs (DCFLs),
closure properties of DCFLs, decidable properties of CFLs,
questions about CFLs that are undecidable, the Turing machine model.
Monday, May 25, 2015:
 The
last homework of the quarter (HW VIII) will be posted on Thursday,
May 28 (instead of Tuesday, May 26), and will be due 4:00 pm on Friday,
June 5 (instead of Wednesday, June 3).
Friday, May 22, 2015:
 To
make Problem 2 in HW7 a bit more interesting, please change the second
transition of M listed on page 184 of the text to
Wednesday, May 20, 2015:
 Lecture 14. Topics covered: More on Pushdown Automata (PDA),
nondeterministic nature of PDA, nulltransitions, manipulating the
stack, Instantaneous Descriptions (IDs) for PDA, definition of the
language accepted by a PDA.
Examples of PDA, Greibach Normal Form, the equivalence of CFLs
and the languages accepted by PDA, deterministic PDA and
deterministic CFLs, closure CFLs under intersection with regular
languages, the problem of trying to simulate the behavior of two stacks with a single stack.
 Reading Assignment: Most material you
need to complete HW7 over the long weekend is available in the textbook
in the sections of "Reading Material" given the past few lectures.
These include worked out examples which parallel the assigned HW
problems.
Tuesday, May 19, 2015:
 HW7 has been posted. It is due on
Wednesday, May 27 at 4:00pm. Homeworks and their posting/due dates can
be accesses through Homework Assignments link above.
Monday, May 18, 2015:
 Lecture 13. Topics covered: More
on closure properties of CFLs, more examples of non CFLs, an inherently
ambiguous CFL, leftrecursion: leftrecursive productions,
leftrecursive variables, elimination of leftrecursion, the Greibach
Normal Form, leftmost derivations and stacks, Pushdown Automata (PDA),
nondeterministic nature of PDA, nulltransitions, manipulating the
stack, Instantaneous Descriptions (IDs) for PDA, definition of the
language accepted by a PDA.
 Reading assignment: 7.1  7.3
Wednesday, May 13, 2015:
 Lecture 12. Topics covered: Applications
of the Chomsky Normal Form (CNF), dynamic programming parsing algorithm
of CockeYoungerKasami (CYK algorithm) for arbitrary CFLs, cubic
running time of CYK, the Pumping Lemma for CFLs, examples of non CFLs,
CFLs are closed under union, concatenation and star closure, CFLs
are not closed under intersection, the CFLs are not closed under complementation.
 Reading Assignment: 7.1, 8.1  8.2.
Tuesday, May 12, 2015:
 HW6 has been posted. It is due on
Wednesday, May 20 at 4:00pm. Homeworks and their posting/due dates can
be accesses through Homework Assignments link above.
Monday, May 11, 2015:
 Lecture 11. Topics covered: Reduced
grammars, the "emptiness problem" is decidable for CFLs, eliminating
null productions, "whether a CFL contains the null word" is decidable,
elimiating unit productions, avoiding cycles, an intermediate normal
form for CFLs without the null word, the Chomsky Normal Form (CNF).
 Reading assignment: 6.3
Sunday, May 10, 2015:
 If you have questions/concerns concerning your midterm exam, grading errors, or request for a regrade, come and see me the week of May 1115. If you cannot make it to the regular office hours, you are welcome to make an appointment.
Thursday, May 7, 2015:
 Here is the histogram of the midterm exam scores: . Some related data are as follows: Lowest score = 44, Average score = 79, Highest score = 100.
Wednesday, May 6, 2015:
 Lecture 10. Topics covered: Few words on midterm questions, parse
(derivation) trees, partial derivation trees, yield of a derivation
tree, tree traversals and derivations, leftmost derivations and
preorder traversal, ambiguity of a CFG, inherent ambiguity of a CFL,
existence of inherently ambiguous CFLs, simplification of CFGs,
productive (active) and reachable variables, botoomup and topdown
generation, eliminating useless variables, reduced grammars.
 Reading assignment: 6.16.2 (excluding the Greibach Normal Form).
Tuesday, May 5, 2015:
 HW5 has been posted. It is due on
Wednesday, May 13 at 4:00pm. Homeworks and their posting/due dates can
be accesses through Homework Assignments link above.
 Reading assignment: 6.16.2 (excluding the Greibach Normal Form).
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 2, 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.
