- [Dec 9] Answers to Homework 7 have been posted.
- [Dec 8] Answers to Homework 8 have been posted.
- [Dec 4] The perm. numbers got mixed up in class, so here are the corrected grade estimations. Here is how to interpret them (let WvD know if things are unclear).
- The first column has the last two digits of your 7 digit perm number (but, if those digits are "04", the column just says "4").
- The next 6 columns contain your homework scores HW1 through HW6.
- Please check these scores: if there is a discrepancy, you should contact the TA about this.
- The columns for HW7 and HW8 are left intentionally blank.
- The next column contains your Midterm score. Please check this one as well.
- The "Est. total" column has your estimated total score extrapolating HWs 1-6 to HWs 7 and 8, and extrapolating your Midterm scores to the Final.
- Hence, its value is: 8/6 times (the sum of the 6 homework scores) plus 3 times the MT score.
- The last column has the corresponding grade estimation.
- [Dec 2] Crucial information on the Final has been posted below.
- [Dec 2] An old CS138 Final has been posted, as well as its answers.
- [Nov 26] Slides of last Tuesday on the pumping lemma for context free languages and the definition of Turing machines have been posted.
- [Nov 26] Happy Halloween: no class on Thursday or Discussion on Friday.
- [Nov 26] Homework 8, "Turing machines", has been posted and is due Wednesday December 3, 3 pm.
- [Nov 19] Homework 7 has been posted and is due Wednesday November 26, 3 pm.
- [Nov 18] Slides of Tuesday Week 8 posted.
- [Nov 18] HW5 is due Wednesday November 19, not Tuesday as it said on the paper.
- [Nov 13] Slides on Context Free Languages (4) have been posted.
- [Nov 12] Homework 6, "Rewriting CFGs", has been posted and is due Wednesday November 19.
- [Nov 7] There will no class on Tuesday November 11, nor will WvD have office hours.
- [Nov 5] Answers to Homework 5 have been posted.
- [Nov 5] Note that there is a small error in the answers to the old Midterm (see below).
- [Nov 3] Answers to Homework 4 have been posted.
- [Nov 2] Answers to example Midterm (Fall 2007) posted.
- [Oct 30] Example Midterm from last year posted.
- [Oct 30] Crucial information on next week's Midterm has been posted below.
- [Oct 30] Slides on Context Free Languages (2 and 3) have been posted.
- [Oct 30] Note that WvD's office hours in Week 6 will be on Monday 1:30-3:30.
- [Oct 28] Homework 5, "Context Free Languages", has been posted and is due Tuesday November 4.
- [Oct 23] Slides of Week 4 have been posted.
- [Oct 22] Homework 4, "Nonregular Languages", has been posted and is due Wednesday October 29.
- [Oct 16] The slides "Regular Languages 2" have been posted.
- [Oct 15] Homework 3, "Regular Languages", has been posted.
- [Oct 14] Note that the Midterm will be in Week 6 on Thursday November 6.
- [Oct 14] The answer to an additional question of the Discussion of Week 2 has been posted.
- [Oct 13] Note that in Question 3 of Homework 2 the relevant alphabet should be {a,b), not {0,1).
- [Oct 9] Updated version 2 of Homework 2 has been posted.
- [Oct 9] The slides "Regular Languages I" have been posted.
- [Oct 9] WvD's office hours have been extended to 1:30-3:30 (Tuesdays).
- [Oct 8] Homework 2, "Finite Automata", has been posted.
- [Oct 2] The introductory slides and those on languages and computation have been posted below.
- [Oct 1] The first homework assignment "Languages" has been posted below. It is due Wednesday October 8, 3 pm in the CS138 homework box in the copy room on the 2nd floor of Harold Frank Hall.
- [Sep 26] The Tuesday and Thursday classes have been moved to Phelps 3505
- [Sep 26] There will be no discussion session on Friday September 26.
- [Sep 21] This course, CS138 uses a reader, which you can buy at The Alternative Copy Shop in IV. Please let me (WvD) know if there are problems with the availability.
- [September 21, 2008] Installment of the website for CS138, Fall 2008.
General Course 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:
- Prerequisite: Computer Science 40; open to computer science and computer engineering majors only.
- Not open for credit to students who have completed Computer Science 136.
Course Information for Fall 2008
Professor:
- Wim van Dam
- vandam@cs.____.___
- Harold Frank Hall, Room 2151
Teaching Assistants:
Required Textbook:
Grading/Exams:
Assignments will be graded using the following scale:
- 10 points: Exemplary; student applies knowledge with virtually no conceptual or procedural errors
- 6 points: Adequate; student applies knowledge with no significant conceptual errors and only minor procedural errors.
- 3 points: 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.
The course grade is determined by: Homework + Midterm + Final = 40% + 20% + 40%
There will be 8 homework assignments, hence each will be worth 5%.
(Tentative) Weekly Schedule:
- Monday: 14:00-16:00: Office hours HY in Phelps 1413
- Tuesday 9:30-10:45: Class in Phelps 3505
- Tuesday 13:30 - 15:30: Office hours WvD in HFH 2151.
- Thursday 9:30-10:45: Class in Phelps 3505
- Friday 11:00-11:50: Discussion in Phelps 1448
- Friday 12:00-12:50: Discussion in Phelps 1448
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 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.
Week 0 (Sep 25 - 28):
- Topics: introduction and formalities, notational conventions
Week 1 (Sep 29 - Oct 5):
Week 2 (Oct 6 - 12):
Week 3 (Oct 13 - 19):
Week 4 (Oct 20 - 26):
Week 5 (Oct 27 - Nov 2):
Week 6 (Nov 3 - 9):
- Topics: normal forms, parsing of CFGs, CYK algorithm
- WvD's office hour is on Monday this week, between 1:30 and 3:30.
- Thursday November 6: Midterm on regular and context free languages
- Information on Midterm
- Midterm from Fall 2007 (note that it does not have questions on CFGs)
- Answers to Fall 2007 Midterm (correction: AC should also be accepting in the answer to Q2a)
Week 7 (Nov 10 - 16):
- Tuesday, November 11: no class and no office hours WvD (Veterans' Day)
- Topics: rewriting CFGs, parsing, Chomsky Normal Form, CYK algorithm
- Homework 6: "Rewriting CFGs" (due Wednesday November 19, 3 pm)
- Slides: Context Free Languages 4
Week 8 (Nov 17 - 23):
- Topics: pushdown automata, languages that are not context free
- Homework 7: "PDAs and Pumping Lemma" (due Wednesday November 26, 3 pm; Answers to HW7)
- Slides: Context Free Languages 5
- Thursday November 20: WvD away; Ömer Egecioglu will be teaching instead
Week 9 (Nov 24 - 30):
- Topics: Turing machines, computability
- Homework 8: "Turing machines" (due Wednesday December 3, 3 pm; Answers to HW8)
- Slides: Pumping Lemma for CFLs and Turing Machines
- Thursday and Friday, November 27-28: no class or discussion (Thanksgiving)
Week 10 (Dec 1 - Dec 5):
Finals Week
- Wednesday, December 10: Final Examination
- time: 8:00 - 11:00 am
- place: PHELPS 3505