Document URL: http://www.cs.arizona.edu/classes/cs473/fall07/
C SC/MATH 473
|
Automata, Grammars and Languages |
| Time and Place | C SC473 Section 001: TR 2:00-3:15, Modern Languages 311 | ||||||||||||||||||||||||||||||
| Honors |
In addition to lecture, the honors section (002) meets:
C SC473H Section 002: R 3:30-4:30, Gould-Simpson 942 |
||||||||||||||||||||||||||||||
| Description | This course is an introduction to the fundamental models of computation used throughout computer science: finite automata, pushdown automata, and Turing machines. The hierarchical relationships among these models, their relative power and limitations, and their variants are studied. Student skills are developed in understanding and using rigorous definition and proof to attack precisely formulated questions about computability and computation. The only successful method known for learning these skills is by working challenging problems, therefore, heavy emphasis is laid upon student problem assignments. The course aims at improving students written communication skills, and serves as a writing emphasis course. The course explores models for and fundamental limitations of the computational process. Proof techniques, major results and computing applications of the results will all be stressed. The material in this course is used in later, more advanced computer science courses. For example, regular expressions and context free grammars are essential in the design of software such as compilers and text processors; and closure properties and nondeterminism are needed to explore inherent intractability (NP-complete problems). Thus every effort is made to (1) motivate concepts with example applications, (2) build a standard vocabulary of concepts and techniques the student will later use frequently, and (3) emphasize the algorithmic and constructive basis of the proofs of results (e.g., regular expression to finite automaton conversion; problem reductions). Topics covered include: finite automata and regular expressions, turing machines, properties of regular sets, Church's thesis, context-free grammars and pushdown automata, decidable and Turing-recognizable sets, properties of context-free languages, universal machines, parsing applications, undecidable problems and reducibility. | ||||||||||||||||||||||||||||||
| Prerequisite | C SC 345: Analysis of Discrete Structures is a mandatory prerequisite. Without 345 or an equivalent from elsewhere (typically entitled "Discrete Mathematics") the likelihood of success in this course is small. We will need specific material and facts from the prerequisite course and, more importantly, the experience with mathematical techniques and methods of thought introduced there, and the ability to use standard language and notation. It is assumed you are familiar with the following topics: trees, graphs, elementary algorithm analysis, induction, recurrence relations, and combinatorics. | ||||||||||||||||||||||||||||||
| Instructor | Peter J.
Downey
pete at cs.arizona.edu (520) 621-2207 Gould-Simpson 739 Office Hour: T 3:30-4:45, R 12:00-1:15 or outside these times by appointment. |
||||||||||||||||||||||||||||||
| Teaching Assistants | Swaminathan Sankararman
swami at cs.arizona.edu 621-4089 Gould-Simpson 710F Office Hour: M 2:00-3:30, W 2:00-3:30 |
||||||||||||||||||||||||||||||
| Andrew Predoehl
predoehl at cs.arizona.edu (520) 621-4089 Gould-Simpson 710A Office Hour: M 11:30-1:00, W 11:30-1:00 |
|||||||||||||||||||||||||||||||
| Text |
Available at UofA Bookstores.
|
||||||||||||||||||||||||||||||
| Course Schedule |
|
||||||||||||||||||||||||||||||
| Course Format |
Grades for this course will be based in the following items:
|
||||||||||||||||||||||||||||||
| C SC Computer Lab Account |
For Everybody: All students are required to fill out the web page entitled Account Service Request at URL www.cs.arizona.edu/~apply. Do so whether or not you already have an account, and whether you are a Computer Science major or not. (This updates a Department database with your course selections, and you can be assigned a correct Computer Science ID (CSID) number). Here is how to proceed: For a student with a currently active account in C SC: At the web page, under Select the Action Desired, select UPDATE an OPEN account for new classes. Fill in other requested information. Read the Appropriate Use Guidelines at www.cs.arizona.edu/policies/computing.html before pushing ACCEPT. For a student without a currently active account in C SC: To obtain a new account on the Department's instructional processor lectura, or to re-activate an existing account, use any machine to go to URL www.cs.arizona.edu/~apply. (During the first week of classes, the Department provides machines for this purpose in Room 930 Gould-Simpson Bldg.) At the web page, under Select the Action Desired, select either NEW account on CS systems, or RE-activate an EXISTING closed CS account. Fill in other requested information. Read the Appropriate Use Guidelines at www.cs.arizona.edu/policies/computing.html before pushing ACCEPT. Your registration information will be verified within a few minutes, and an account will be created for you, along with a keycard allowing round-the-clock lab access. The keycard will be available in Room 930 while the account registration machines are set up there, and at the Reception Desk in Room 917 thereafter. For Everybody: You will need to know your CSID. To find your CSID at any time, go to www.cs.arizona.edu/computing/services/csid.html. Enter your 9-digit Student ID (SID) without any hyphens, and push the submit button. Record your CSID for future reference. Grades will be posted using your CSID. |
||||||||||||||||||||||||||||||
| Policies |
Each graded item, such as a homework or examination, is first awarded a raw score; raw scores vary with the number of questions, their difficulty, and their length. For each graded item, the raw score is normalized to a traditional scale in which 90 - 100 is an A, 80 - 89 is a B and 70 - 79 is a C. For each graded item, only the normalized score is recorded. The final cumulative course grade is computed as a weighted average of these normalized scores, using the weights described under Course Format above. The resulting weighted average is then converted to a letter grade using the traditional scale. Decisions on whether borderline scores (such as 79) will be recorded as the next highest letter grade will be made using (a) performance on the final examination and (b) evidence of accomplishment in the subject that is cumulative over the term. Attendance is not enforced, but you are responsible for all material covered in lecture or assigned as reading. Arriving late to class is rude and disruptive; if you cannot arrive on time, do not bother to come. Without prior arrangements, missed exams result in a grade of zero. Homework is due at the start of class on the due date; late homework is not accepted. It is assumed that: you have the prerequisites for this course, and their prerequisites, etc., recursively. The instructor reserves the right to fail for the course any student failing the final comprehensive examination, irrespective of the final weighted average. The content of this syllabus is subject to change at the discretion of the instructor. |
||||||||||||||||||||||||||||||
| Academic Integrity |
Assignments
in this course require individual attention and effort to be of any benefit.
All work is expected to be that of each student alone, without
consultation with others, without reference to borrowed solutions
and not the product of team efforts or collaboration with other authors.
Plagiarism is the incorporation of someone else's words or ideas without
proper attribution, whether taken from another student, an author, the
instructor's published solutions or the Internet.
Plagiarism
constitutes theft of intellectual property, and those who engage
in it will receive the failing grade of ``E''.
These and other provisions are governed by the
University's
Code of Academic
Integrity
which applies to all those in this course.
|
Assignment Format |
All written work submitted for credit must be prepared using a program capable of producing typeset output with the appropriate type faces, symbols and notation used in the theory of computation (e.g., TeX, LaTeX, troff, Microsoft Word + Equation). Do not submit handwritten work. However, figures and diagrams may be rendered by hand if neat and clearly labeled, although it is preferable to use a drawing tool like xfig, picasso, etc. Start each solution on a new page, repeat the problem statement, and number each page. Write on one side of the paper only. Submit answers in the labeled manila envelope (provided in class) on or before the due date. Do not seal the envelope in order that it may be reused. Write concise and clear solutions, since failure to communicate clearly will cost points whether or not the conclusion is correct. Remember that this is a Writing Emphasis Course, and work will be graded in part on the quality of your writing, not just on its technical content. All good writing is based upon revision. It is essential to revise your work before submission, and to consider whether your argument will be understandable to the reader. For example, it is never a waste of effort to explain the strategy you intend to use in a proof or construction, before beginning to present the work in detail. Think of the reader. Explain as if teaching a colleague in your class. Revise. Revise again. |
||||||||||||||||||||||||||||
| Accommodation |
Students with disabilities, who may require academic adjustments or reasonable accommodations in order to participate fully in course activities or to meet course requirements, must first register with the Disability Resource Center, 1540 E 2nd St, 621-3268, email drc@w3.arizona.edu, URL http://drc.arizona.edu. DRC staff will qualify students for services, and provide a letter to the instructor listing accommodations to be made. This letter should be submitted by the student directly to the instructor as soon as possible during the first week of classes. The student should meet as soon as possible with the instructor by appointment or during office hours to discuss accommodations and how course requirements and activities may impact your ability to fully participate. |
||||||||||||||||||||||||||||||
| Syllabus |
|
||||||||||||||||||||||||||||||
| Lecture Slides |
When lecture slides are available, PDF versions are placed here.
|
||||||||||||||||||||||||||||||
| Homework |
Exams
|
|
|