CS138, UCSB, 2013-09/12

Recent Announcements

  • 2013-12-23: We're done. Happy Holidays.

General CS138 Information

  • Course no.: CS 138
  • Course title: Automata and Formal Languages
  • Total credits: 4
  • Description: Formal languages; finite automata and regular expressions; properties of regular languages; pushdown automata and context-free grammars; properties of context-free languages; introduction to computability and unsolvability (Turing machines) and computational complexity.
  • Prerequisites: Computer Science 40; open to computer science and computer engineering majors only.
  • CS138 is not open for credit to students who have completed Computer Science 136.

Fall 2013 CS138 Information

  • Professor:
    • Wim van Dam
    • vandam@cs.____.___
    • Harold Frank Hall, Room 2151
  • Teaching assistants:
    • Erdinc Korpeoglu
    • korpeoglu@cs.____.___
    • Steven Bluen
    • sbluen153@yahoo.com

Reader

This course has a required reader that will be available at The Alternative.

For those who can't wait: the first week or so we will be using Chapter 1, pp. 1--35 from John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, second edition, Addison-Wesley (2001), which you should be able to get in the library.

Weekly Schedule, Typical

  • Monday
    • 13:00--15:00: Office hours SB (Graduate Student Lab, Rm 698)
  • Tuesday
    • 10:00--11:00: Office hour WvD (HFH 2151)
    • 12:30--13:45: Class (PSYCH 1902)
    • 16:00--16:50: Discussion (GIRV 1116)
    • 17:00--17:50: Discussion (387 103)
  • Wednesday
  • 15:00--17:00: Office hours EK (Graduate Student Lab, Rm 698)
  • Thursday
  • 10:00--11:00: Office hour WvD (HFH 2151)
    • 12:30--13:45: Class (PSYCH 1902)
  • Friday
    • Homework due at 16:00
    • Announcement of Homework at 23:59

Grading

Assignments will be graded using the following scale:

  • 6 points: Exemplary; student applies knowledge with virtually no conceptual or procedural errors
  • 4 points: Adequate; student applies knowledge with no significant conceptual errors and only minor procedural errors.
  • 2 point: Minimal; student applies knowledge with occasional conceptual errors and only minor procedural errors.
  • 0 points: Unsatisfactory; student makes significant conceptual and/or procedural errors when applying knowledge.

Your grade for the course is determined as follows.

  • The 6 Homeworks and 1 Midterm all count for an equal amount; the final counts for 2 Homeworks. This means that your total grade will be determined according to: 6 Homeworks + 1 Midterm + 1 Final = 6/9 + 1/9 + 2/9. In other words, each homework and midterm counts for 1/9th, the final counts for 2/9th.
  • However, during the Final you are allowed to decide whether you want to drop your lowest score among your homeworks and midterms and let your final count for 3/9th, in which case the equality becomes: 5 Homeworks + 1 Midterm + 1 Final = 5/9 + 1/9 + 3/9 or 6 Homeworks + 0 Midterm + 1 Final = 6/9 + 0/9 + 3/9.

Means and Standard Deviations of HWs, MTs, and F

To calculate your 'normalized score', you take your score, subtract the mean, and divide by the standard deviation.

Academic Honesty

The following applies to every course you attend at UC Santa Barbara (from UCSB Campus Regulations, Chapter VII: "Student Conduct and Discipline"):

It is expected that students attending the University of California understand and subscribe to the ideal of academic integrity, and are willing to bear individual responsibility for their work. Any work (written or otherwise) submitted to fulfill an academic requirement must represent a student’s original work. Any act of academic dishonesty, such as cheating or plagiarism, will subject a person to University disciplinary action. Using or attempting to use materials, information, study aids, or commercial “research” services not authorized by the instructor of the course constitutes cheating. Representing the words, ideas, or concepts of another person without appropriate attribution is plagiarism. Whenever another person’s written work is utilized, whether it be a single phrase or longer, quotation marks must be used and sources cited. Paraphrasing another’s work, i.e., borrowing the ideas or concepts and putting them into one’s “own” words, must also be acknowledged. Although a person’s state of mind and intention will be considered in determining the University response to an act of academic dishonesty, this in no way lessens the responsibility of the student.

Specifically for the current CS138 course this means that

  • You are not allowed to copy or transcribe answers to homework assignments from others or other sources.
  • Although you are allowed to discuss homework assignments with others, you should write down your answers independently. You should always be able to argue and explain your answers when asked for clarifications.
  • During the Midterm and Final Examination no electronics are allowed, additional notes are only allowed to the extent described prior to the test.
  • When you will be unable to hand in the homework in time you should report this to WvD as soon as possible, but always before the deadline. No matter the reason, you will always be asked to present documentation.
  • When in doubt, ask.
  • Students violating the rules of Academic Honesty will receive an "F" for the course and will be reported to the Dean of Students Office.

Schedule of Topics, Homeworks, Midterms, and Final

Week nulla [09-26/09-29]

  • First Class on Thursday, September 26, 12:30--13:45
  • Class topics: formalities; [R, pp. 1--16]: introduction to CS138, proof techniques, set theory, formal languages, defining problems as the decision problem of recognizing the words of a formal language
  • Friday: announcement HW1 "Formal Languages"

Week I [09-30/10-06]

  • Class topics, Tuesday: [R, pp. 16--20] concatenation, operations on languages, reducing general problems to decision problems
  • Class topics, Thursday: [R, pp. 22--30] finite automata, formal definition of FA, regular languages, regular operations, closure properties of RLs
  • First Discussions on Tuesday, October 1, 16:00--16:50 and 17:00-17:50
  • Discussion topics [EK]: HW1 "Formal Languages"
  • Friday: HW1 due; announcement of HW2 "Deterministic Finite Automata"

Week II [10-07/10-13]

  • Class topics: [R, pp. 30--38]: nondeterminism, nondeterministic FA, proof that every NFA is equivalent to a DFA, closure of RLs under union, concatenation, and star; [R, pp. 38--45]: regular expressions, RE≤RL, generalized NFA, RE=R
  • Discussion topics: HW2
  • Friday: HW2 due; announcement of HW3 "NFA and Regular Languages"

Week III [10-14/10-20]

  • Class topics: [R, pp. 45-48]: non-regular languages, pumping lemma for RLs, proving non-regularity using the pumping lemma
  • Discussion topics: HW3, return of HW1
  • Friday: HW3 due; announcement of HW4 "Nonregular Languages"

Week IV [10-21/10-27]

  • Class topics: [R, pp. 58--70]: Context free grammars, derivation trees, parsing, ambiguity, CFGs and programming languages; [R, pp. 72-76]: transforming grammars, removing useless productions
  • Discussion topics: HW4, return of HW2
  • Friday: HW4 due

Week V [10-28/11-03]

  • Class topics: [R, pp. 72-78]: transforming grammars, removing lambda-reductions, removing unit-productions; [R, pp. 80--84]: Chomsky Normal Form, (Greibach Normal Form), CYK algorithm for membership for CFGs
  • Discussion topics: Return of HW3; Midterm
  • Thursday October 31: Halloween Midterm on formal languages, finite automata, regular languages, and context free grammars
  • Material: Reader pp. 1--70; Slides: Formal Languages, Finite Automata, Regular Expressions, Non Regular Languages, CFLs; HWs 1--4.
  • The location and time of MT are those of a regular class: Psych 1902, between 12:30 and 13:45 pm
  • You are allowed to bring one, letter-sized, double-sided page of notes.
  • You are not allowed to bring any other notes like the reader, nor are you allowed to use electronic devices like iPhones, calculators, etc.
  • Remember that one Midterm counts as much as one Homework
  • During Tuesday's class you can ask questions about this midterm

Week VI [11-04/11-10]

  • WvD's office hour on Tuesday 2013-11-06 is between 11:00 and 12:00
  • Class topics: [R, pp. 80--84]: Chomsky Normal Form, (Greibach Normal Form), CYK algorithm for membership for CFGs; [R, pp. 104--106]: non-CFLS, pumping lemma for CFLs, proving languages to be non CFLs using the pumping lemma; [R, 88-102] Pushdown Automata, PA and CFLs, deterministic PAs and deterministic CFLs
  • No Discussion
  • Friday: announcement of HW5 "Parsing, Non CFLs, PAs"

Week VII [11-11/11-17]

  • Monday, November 11: Veteran's Day
  • Class topics: [R, 88-102] Pushdown Automata, PA and CFLs, deterministic PAs and deterministic CFLs; [R, pp. 112--116]: Turing Machines, Church-Turing Thesis, computability, universality and self-reference of TMs;
  • Discussion topics: HW5; return of Midterm
  • Friday: HW5 due; announcement of HW6 "PAs, TMs"

Week VIII [11-18/11-24]

  • Class topics: [R, pp. 112--116]: [R, pp. 116-122]: decidable problems, Universal TM, undecidability of the Halting Problem, proof by diagonalization, semi-decidable problems
  • Discussion topics: HW6
  • Friday: HW6 due

Week IX [11-25/12-01]

  • Class topics: [R, pp. 123--128]: recursive and recursively enumerable properties, more decidable and undecidable problems, computability theory
  • Discussion topics: return of HW5, answers to HW6
  • Thursday November 28: No class
  • Thursday and Friday, November 28 and 29: Thanksgiving

Week X [12-02/12-06]

  • Class topics: wrap-up "How do the topics of CS138 fit into computer science?", preview of Final, "You and your grade", course evaluation; Q&A on Final
  • Discussion topics: return of HW6; Final
  • No office hours of EK on Wednesday. Instead, EK will have his office hours on Friday, 13:00--15:00 (Graduate Student Lab, Rm 698)

Finals Week [12-07/12-13]

  • Final Examination: Monday November 9, 12:00--15:00