CPSC 433: Formal Languages and Automata
- 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
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
- 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
- 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
- 3/2: Homework 4 is now available, due
- 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
4.1.1(d) 5 (e) 5 (f) 5
4.1.2(d) 10 (g) 10 (h) 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
- 2/2: Details on the programming part of
HW 2 are now available.
- 2/1: Homework 2 is now available, due
- 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
- 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
- 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
- 1/17: Mu-Fen's email address was incorrect on the syllabus
handed out in class today. Her correct address is firstname.lastname@example.org.
Back to beginning
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*)
Office Phone: 845-5820
Office: 329 H.R. Bright Bldg
Office Hours: Mondays, Wednesdays, Fridays 3:00 - 4:00 PM;
other times by appointment.
Office Phone: 845-0269
CPSC 311, Analysis of Algorithms.
Tuesdays and Thursdays, 12:45 - 2:00 PM, HRBB 113.
Introduction to Automata Theory, Languages and Computation,
Hopcroft, Motwani and Ullman, Addison Wesley, 2001.
Course Content and Tentative Schedule:
The course will cover the following topics.
- To introduce you to the theoretical foundations of computer
- 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
| week of
|| Introduction and Math Preliminaries
|| Ch. 1
|| Finite Automata
|| Ch. 2
| 1/31, 2/7
|| Regular Expressions and Languages
|| Ch. 3
|| Properties of Regular Languages
|| Ch. 4
|| Context-Free Grammars and Languages
|| Ch. 5
| 2/28, 3/7
|| Push-Down Automata
|| Ch. 6
|| SPRING BREAK
| 3/21, 3/28
|| Properties of Context-Free Languages
|| Ch. 7
|| Turing Machines
|| Ch. 8
|| Ch. 9
| 4/18, 4/25
|| Ch. 10
Assignments and Grading:
All assignments will be announced in class and posted on the web page
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 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
Please discuss unusual circumstances in advance
with the instructor.
Course grades will be assigned according to this scale:
| percent of total points
|| < 60
| letter grade
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
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
statute that provides comprehensive civil rights protection for
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
This calendar lists all due dates as they become known for
Follow the links to get
- culture activities
- details on the assignments
- exam reviews
| 1/17 |
| 1/18 |
| 1/19 |
Read Chs 1 and 2
| 1/20 |
| 1/23 |
| 1/24 |
NFAs; Conversion from NFA to DFA
| 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
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;
Read Ch 5
| 2/10 |
| 2/13 |
| 2/14 |
Chomsky Normal Form
Read Ch 7, Sec 1
HW 2 due
| 2/15 |
| 2/16 |
More Chomsky Normal Form
Culture 2 due
| 2/17 |
| 2/20 |
| 2/21 |
HW 3 due
| 2/22 |
| 2/23 |
| 2/24 |
| 2/27 |
| 2/28 |
Read Ch 7
| 3/1 |
| 3/2 |
PDAs and CFGs
| 3/3 |
| 3/6 |
| 3/7 |
Pumping Lemma for CFLs
| 3/8 |
| 3/9 |
Pumping Lemma for CFLs
Culture 3 due
| 3/10 |
| 3/13 |
| 3/14 |
| 3/15 |
| 3/16 |
| 3/17 |
| 3/20 |
| 3/21 |
Properties of CFLs
HW 4 due
| 3/22 |
| 3/23 |
Read Ch 8
| 3/24 |
| 3/27 |
| 3/28 |
TMs and Church-Turing Thesis
Read Ch 9
| 3/29 |
| 3/30 |
Undecidability; A Non-RE Language
Culture 4 due
| 3/31 |
| 4/3 |
| 4/4 |
HW 5 due
| 4/5 |
| 4/6 |
| 4/7 |
| 4/10 |
| 4/11 |
A Non-Recursive Language
| 4/12 |
| 4/13 |
| 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
- 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
Computing-Related at TAMU
Careers and Mentoring
Back to beginning