CPSC 433: Formal Languages and Automata
Spring 2006

Announcements

• 5/9: You can pick up the remaining graded assignments (Quizzes 11 and 12, culture 5, program 2, HW 6) from my office today. I will bring anything not picked up to the final exam tomorrow morning.

• 4/27: Review for final exam is now available.

• 4/20: Additional problems (on NP-completeness) have been added to Homework 6 (due Apr 27). The assignment is now complete.

• 4/20: You will do the evaluations for this course on line instead of on paper. Here are the instructions: go to https://pica.tamu.edu, click on "Student Login" and log in using your neo id and password. See the FAQ for answers to questions regarding confidentiality and how your feedback will be used. YOU MUST DO THE EVALUATION BETWEEN APRIL 21 AND MAY 4.

• 4/14: Homework 6 is now available, due Apr 27.

• 4/12: Extension for Program 2: I'm extending the due date to 12:45 PM on Tuesday, April 18.

• 4/12: If you got 0 points on Quiz 8 (pumping lemma for CFL problem) because you used the wrong language (e.g., k^3 instead of 3^k), you can turn it back in for regrading and partial credit.

• 4/12: The output requirements for Program 2 have been clarified.

• 4/2: CORRECTION! Prof. Towsley's distinguished lecture is on Monday, Apr 17, not Monday, Apr 3. If you have already made preparations to attend the seminar tomorrow (Apr 3), which is by Dr. Xiliang Liu, you may write a report on his seminar instead of on Prof. Towsley's. Sorry for the confusion.

• 4/2: Several announcements:
  • Review for Exam 2 is now available. You can bring one page of notes to the exam.
  • No quiz this coming Tuesday (4/4).
  • My office hours this week will be Wednesday 8:45 - 10:15 (as usual) and Thursday 10:00 - 11:30 (for last minute test questions, instead of Monday's hours). Email if you need to meet at another time.

• 3/28: HW 5 is now available, due April 4. Program 2, part of HW 5, is due April 13.

• 3/27: Sorry for the late notice, but my office hours today (Mon, Mar 27) are cancelled. Please email me if you need to meet with me.

• 3/20: Mu-Fen's office hours on Wed, Mar 22, will be 4:00 - 5:00 instead of as regularly scheduled.

• 3/15: Nonstandard office hours for the week of Mar 20-24: They will be Tue, Mar 21, 2:00 - 3:45 PM and Fri, Mar 24, 9:00 - 10:00 AM. If you need to see me before class on Tue, Mar 21, please email me and I will work it in.

• 3/9: Additional problems (on the pumping lemma for CFL's) have been added to Homework 4 (due Mar 21). The assignment is now complete.

• 2/2: Peter Naur wins ACM 2006 Turing Award! He was a major contributor to the first programming language definition that, instead of using English prose and the compiler itself to define the language, introduced and used Backus-Naur Form to describe context-free grammars.

• 3/2: Homework 4 is now available, due Mar 21.

• 2/27: Reminder that Culture Report 3 (due Thu, 3/9) is to be either on the Distinguished Lecture by Prof. Leah Jamieson (Mon, 3/6, 4:10) or on one of her papers.

• 2/27: This week's quiz (Quiz 6) will be on Thursday (Mar 2) instead of Tuesday (Feb 28).

• 2/21: Regarding the grading on HW 2: the program is not yet graded so the 120 points does not include the program. Here is the point breakdown:

  3.1.1(b) 5 (c) 10
  3.1.2(b) 5
  3.2.3 10
  3.2.4(C) 5
  4.1.1(d) 5 (e) 5 (f) 5
  4.1.2(d) 10 (g) 10 (h) 10
  4.1.4 10
  4.2.6(c) 10
  4.2.13(b) 10
  4.3.2 10
  
  Total 120 points
  

• 2/16: Review for Exam 1 is now available. Note that you can bring one page of notes to the exam.

• 2/14: Homework 3 is now available, due Feb 21.

• 2/2: Details on the programming part of HW 2 are now available.

• 2/1: Homework 2 is now available, due Feb 14.

• 1/30: For Exercise 2.2.5 (b) (tenth symbol from the end is a 1), don't try to draw the DFA. Instead, you can give an example with a smaller value than 10, and explain the pattern that you would follow for 10.

• 1/30: There is a free software package called JLAP that is "a package of graphical tools which can be used as an aid in learning the basic concepts of Formal Languages and Automata Theory." You can use it to help you visualize what is going on with DFAs, NFAs, regular expressions, converting between the different formalisms, as well as context-free languages and Turing machines.

  Mu-Fen and I recommend that you use JFLAP in the following ways to help you with your homework:

  • You can print the intermediate results of the computation of your machine on a particular input.
  • It can automatically do the conversion of an NFA to a DFA, so you can check if you are doing it correctly.
  • It can help you understand the operation of the the different kinds of machines (head movement, reading and writing the stack/tape) through visualization, especially when we get to PDAs and Turing machines.
  • JFLAP can help you to test and revise your answers, when designing a DFA, NFA, PDA or TM for a complicated language. Sometimes it's hard to simulate the behavior (especially of PDAs and TMs) by hand, and JFLAP can provide automated help.

  To use JFLAP, you download it onto your computer. It requires Java. Please check with Mu-Fen if you have questions regarding JFLAP -- she has been experimenting with it quite a bit.

• 1/25: For culture 1, you can do a paper that appeared in December 2005.

• 1/25: Dr. Welch's office hours are changed: they are Mondays 2:00 - 3:30 PM and Wednesdays 8:45 - 10:15 AM. This is a permanent change for the semester.

• 1/19: Homework 1 is now available, due Jan 31.

• 1/17: Mu-Fen's email address was incorrect on the syllabus handed out in class today. Her correct address is mufen@tamu.edu.

Back to beginning

Syllabus

Teaching Assistant: Mu-Fen Hsieh
Office: 329 H.R. Bright Bldg
Office Hours: Mondays, Wednesdays, Fridays 3:00 - 4:00 PM; other times by appointment.
Email: mufen@tamu.edu
Office Phone: 845-0269

Prerequisite: CPSC 311, Analysis of Algorithms.

Lecture: Tuesdays and Thursdays, 12:45 - 2:00 PM, HRBB 113.

Textbook: Introduction to Automata Theory, Languages and Computation, 2nd ed., Hopcroft, Motwani and Ullman, Addison Wesley, 2001.

Course URL: http://www.cs.tamu.edu/faculty/welch/teaching/433.s06

• To introduce you to the theoretical foundations of computer science concerning
  • the relationships between languages and machines
  • the inherent limits of what can be computed
  • the inherent efficiency of solving problems
• To familiarize you with the applications of these theoretical topics to practical problems
• To increase your ability to recognize and create rigorous mathematical arguments

Your grade will be based on four components:

• exams 60% - There will be two mid-term exams and one final exam, each worth 20%. The exams will be held in class.

• quizzes 10% - There will be 12 short weekly quizzes, consisting of a few simple questions (short answer, true-false, or multiple choice) concerning the reading and/or the material covered in the last class. The purpose of the quiz is to encourage you to do the reading in advance and to stay caught up in the class. Your lowest two quiz grades will be dropped.

• homework 25% - Pencil and paper exercises and programming assignments.

• culture 5% This component is to round out your classwork. Find, read, and write short reports on five technical papers in computer science journals. An alternative to some of the journal paper reports will be to attend a lecture and write a short report on it. More details are here.

No late assignments will be accepted. There will be no make-up exams except for university-excused absences. Please discuss unusual circumstances in advance with the instructor.

Course grades will be assigned according to this scale:

Collaboration: For the assignments in this class, discussion of concepts with others is encouraged, but all assignments must be done on your own, unless otherwise instructed. If you use any source other than the text, reference it/him/her, whether it be a person, a book, a solution set, a web page or whatever. You MUST write up the solutions in your own words. Copying is strictly forbidden. Every assignment must be turned in with this cover sheet, which lists all sources you used.

Americans with Disabilities Act (ADA) Policy Statement: The Americans with Disabilities Act (ADA) is a federal antidiscrimination statute that provides comprehensive civil rights protection for persons with disabilities. Among other things, this legislation requires that all students with disabilities be guaranteed a learning environment that provides for reasonable accommodation of their disabilities. If you believe you have a disability requiring an accommodation, please contact the Department of Student Life, Services for Students with Disabilities in Cain Hall, Rm. B118, or call 845-1637.

Back to beginning

Calendar

• readings
• quizzes
• homework
• exams
• culture activities

• details on the assignments
• exam reviews

Back to beginning

Culture Activities

You are to find, read, and write short reports on three technical papers in computer science journals. Articles in the following two journals are usually at about the right level:

• Communications of the ACM
• IEEE Computer

Each report is to be one to two pages long, typed, and must include

• correct bibliographic information for the paper (title of article; names of all authors; name of journal with volume, number, date and page numbers)
• a summary of the paper contents
• at least one comment about the paper or question that it raised in your mind, indicating that you have thought critically about the material
• filled-in cover sheet
• a photocopy of the original article attached

For two of the culture reports, you will have the opportunity to attend a lecture and write up a short report (including cover sheet, title of talk, name and affiliation of speaker, date of talk, summary of talk, and at least one comment or question as for the journal paper reports). These opportunities Distinguished Lecturer Series. If you have a schedule conflict with the lectures, you may substitute a report on a journal article written by the distinguished lecturer.

DO NOT PLAGIARIZE! You must write up your summary in your own words. See academic integrity policy in the syllabus.

Here are some tips for getting full credit on your reports.

Distinguished Lecture dates and report due dates are indicated in the calendar and reproduced here for convenience:

• Culture report 1 due Thu, Jan 26, on journal article of your choice
  
• Culture report 2 due Thu, Feb 16, on journal article of your choice
  
• Distinguished Lecture by Leah Jamieson, Purdue Univ., Mon, Mar 6, 4:10 PM in 124 Bright
  
• Culture report 3 due Thu, Mar 9, on Jamieson lecture/paper
  
• Culture report 4 due Thu, Mar 30, on journal article of your choice
  
• Distinguished Lecture by Don Towsley, Univ. of Massachusetts, Mon, Apr 17, 4:10 PM in 124 Bright
  
• Culture report 5 due Thu, Apr 20, on Towsley lecture/paper

Back to beginning

Useful Links

• Web site for the textbook

• JFLAP web site

• Turn-in program information

Computing-Related at TAMU

• Texas A&M Computing Society (TACS) -- student organization for those interested in computing. Affiliated with the two main professional organizations, ACM and IEEE Computer Society.

• Computer Science Department, TAMU

• Student Computing and Information Page: central source of information about student computing at TAMU.

• Schedule of short courses offered by the CIS Computer Help and Training Group.

Careers and Mentoring

• Office of Honors Programs and Academic Scholarships

• CS Department Student Research Information

• TAMU Co-operative Education

• Computing Research Association Distributed Mentor Project for Undergraduate Females in Computer Science and Engineering: If you think you might be interested in graduate school in CS or CE, this could be a great opportunity for you if/when you are a sophomore or junior. Be thinking ahead!

Back to beginning