UCSB
COMPUTER SCIENCE 138: 
Automata and Formal Languages
Spring 2015

                                                         
SyllabusHomework Assignments                                     
Instructor: 
Omer Egecioglu
omer@cs.ucsb.edu,

Teaching Assistants:
Mohammad Javad Amiri
amiri@cs.ucsb.edu

John Retterer-Moore
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:
text
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.1-9.3, 10.1-10.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, null-transitions, 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, left-recursion: left-recursive productions, left-recursive variables, elimination of left-recursion, the Greibach Normal Form, leftmost derivations and stacks, Pushdown Automata (PDA), nondeterministic nature of PDA, null-transitions, 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 Cocke-Younger-Kasami (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 11-15. 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, botoom-up and top-down generation, eliminating useless variables, reduced grammars.
  • Reading assignment: 6.1-6.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.1-6.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:00-5:00 pm in Phelps 3526.
  • You can check the piazza for solutions to the practice exam that John may post.
  • Lecture 9. Topics covered: Context-free grammars and context-free languages, sentential forms, direct derivations, derivations, A-productions, null-productions, unit-productions, examples of context-free languages and grammars, grammars for the languages NOAA, PALIN, DYCK and EQUAL, derivation as graph reachability, brute force parsing in 2|w| 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:00-12:50. 
  • I will have additional office hours tomorrow (Thursday,April 23) 10:00-11: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:00-12: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 word-transitions, 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, star-closure, 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 star-closure.
  • 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, 5-tuple definition, Deterministic Finite Automata (DFA), the language accepted by a DFA,regular languages, complementation, Non-deterministic 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:00-3: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 2-letter 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:00-6:00 pm on Tuesdays in TRAILER 936 (instead of 4:40-6:30 pm as given in the syllabus handed out the first day of classes). 
  • Lecture 2. Topics covered: Concatenation of languages, star-closure and positive closure, prefixes, suffixes; proper prefixes, proper suffixes, algebra-like 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, non-commutativity.
  • Reading assignment: pp. 1-27.
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 2-hour check-out.
  • 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.