CPSC 433: Formal Languages and Automata
Spring 2006
[Announcements]
[Syllabus]
[Calendar]
[Culture Activities]
[Useful Links]
 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 NPcompleteness)
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: MuFen'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 2024:
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 BackusNaur Form to describe contextfree
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 contextfree
languages and Turing machines.
MuFen 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 MuFen 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: MuFen's email address was incorrect on the syllabus
handed out in class today. Her correct address is mufen@tamu.edu.
Back to beginning
Instructor:
Prof. Jennifer Welch
Office: 415 H.R. Bright Bldg
Office Hours: Mondays 2:00  3:30 PM and Wednesdays 8:45  10:15 AM;
other times by appointment (*updated on 1/25*)
Email: welch@cs.tamu.edu
Office Phone: 8455820
Teaching Assistant:
MuFen 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: 8450269
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
Course Goals:
 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
Course Content and Tentative Schedule:
The course will cover the following topics.
week of
 topic
 reading

1/17
 Introduction and Math Preliminaries
 Ch. 1

1/24
 Finite Automata
 Ch. 2

1/31, 2/7
 Regular Expressions and Languages
 Ch. 3

2/14
 Properties of Regular Languages
 Ch. 4

2/21
 ContextFree Grammars and Languages
 Ch. 5

2/28, 3/7
 PushDown Automata
 Ch. 6

3/14
 SPRING BREAK
 .

3/21, 3/28
 Properties of ContextFree Languages
 Ch. 7

4/4
 Turing Machines
 Ch. 8

4/11
 Undecidability
 Ch. 9

4/18, 4/25
 NPCompleteness
 Ch. 10

Assignments and Grading:
All assignments will be announced in class and posted on the web page
calendar.
If you miss class for any reason, it is your responsibility to find
out what assignments you missed.
Your grade will be based on four components:
 exams 60% 
There will be two midterm 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, truefalse, 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 makeup exams
except for
universityexcused absences.
Please discuss unusual circumstances in advance
with the instructor.
Course grades will be assigned according to this scale:
percent of total points
 90100
 8089
 7079
 6069
 < 60

letter grade
 A
 B
 C
 D
 F

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 8451637.
Back to beginning
This calendar lists all due dates as they become known for
 readings
 quizzes
 homework
 exams
 culture activities
Follow the links to get
 details on the assignments
 exam reviews
Monday
 Tuesday
 Wednesday
 Thursday
 Friday

1/16
MLK Holiday
 1/17
Introduction
 1/18
 1/19
DFAs
Read Chs 1 and 2
Quiz 1
 1/20

1/23
 1/24
NFAs; Conversion from NFA to DFA
Quiz 2
 1/25
 1/26
More Conversion; Regular Expressions
Read Ch 3
Culture 1 due
 1/27

1/30
 1/31
Conversions Between Regular Expressions and NFAs
Quiz 3
HW 1 due
 2/1
 2/2
Pumping Lemma for Regular Languages
Read Ch 4
 2/3

2/6
 2/7
More Pumping Lemma;
Properties of Regular Languages
Quiz 4 2/8
 2/9
More Properties of Regular Languages;
ContextFree Grammars
Read Ch 5
 2/10

Monday
 Tuesday
 Wednesday
 Thursday
 Friday

2/13
 2/14
Chomsky Normal Form
Read Ch 7, Sec 1
Quiz 5
HW 2 due
 2/15
 2/16
More Chomsky Normal Form
Culture 2 due
 2/17

2/20
 2/21
Review
HW 3 due
 2/22
 2/23
Exam 1
 2/24

2/27
 2/28
PushDown Automata
Read Ch 7
 3/1
 3/2
PDAs and CFGs
Quiz 6
 3/3

3/6
DLS: Jamieson
 3/7
Pumping Lemma for CFLs
Quiz 7
 3/8
 3/9
Pumping Lemma for CFLs
Culture 3 due
 3/10

3/13
SPRING BREAK
 3/14
SPRING BREAK
 3/15
SPRING BREAK
 3/16
SPRING BREAK
 3/17
SPRING BREAK

Monday
 Tuesday
 Wednesday
 Thursday
 Friday

3/20
 3/21
Properties of CFLs
Quiz 8
HW 4 due
 3/22
 3/23
Turing Machines
Read Ch 8
 3/24

3/27
 3/28
TMs and ChurchTuring Thesis
Read Ch 9
Quiz 9
 3/29
 3/30
Undecidability; A NonRE Language
Culture 4 due
 3/31

4/3
 4/4
Review
HW 5 due
 4/5
 4/6
Exam 2
 4/7

4/10
 4/11
A NonRecursive Language
Quiz 10
 4/12
 4/13
Rice's Theorem
 4/14
READING DAY  NO CLASSES

Back to beginning
There is a lot more to Computer Science than you will be exposed
to through your normal coursework.
The purpose of the CS culture activities is to give you an
opportunity to learn about current trends in computing.
Keeping up with industry trends and learning to evaluate critically
what you read are valuable professional skills.
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:
Both are in the library; if you click on the journal titles, you will
get to the ACM and IEEE Computer Society
digital libraries respectively (if you are
behind the TAMU firewall).
Each article must have been published after Jan 1, 2006.
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
 filledin 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
CourseRelated
ComputingRelated at TAMU
Careers and Mentoring
Back to beginning