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
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: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.