CS 445-60 Theory of Computation - Automata Theory / Formal Languages -- Spring 2000
SYLLABUS

Instructor: Richard Varron, Programmer I, WPUNJ                                     Phone: 1-973-720-3307
Section: CS 445-60                                                                                     Time: W 7:00pm-9:40pm
Room:  Y 114                                                                                                Mailbox: Atrium
Office Hours: M-F 12:30-1:30 (College Hall 220 call first), before class (anytime from 3:00pm on) or  by appointment.
E-Mail:                                         rich@wpc.wpunj.edu
E-Mail For Non-text Material:  varronr@wpunj.edu
Prerequisites: Data Structues:CS342, (C- or better) 
                       Computer Science II: CS240, (C- or better)
                       Discrete Structures: CS260 (C- or better) [esp. ch 6,7,8 and 10]

The mid-term exam is HERE, WORD97, PDF. The answers are here.

NEW/UPDATED notes are marked with NEW+date on the Notes page.

Detailed answer for ch24 #12 (PDF)

  
    What I want to do on April 19 and April 26 is to have you break into groups of 2's and work on some practice problems. This will give you some practice for the final. I want you to start to focus on putting together the topics we covered in class this semester. The questions (which are of the flavor and difficulty as those on the final) are 

ch 19 #3(i) #19(i)
ch 22 #7, #12
ch 23 #2, #10(i), #11
ch 24 #4(i), #12 

Hint for the final: Since you will be asked only one question, make sure that you familiar with the answers for all the questions on the final. [If you get stuck during the preparation week, e-mail me.] The questions on the final break out as follows:

• 3 proofs - all of which can be done in one or two sentences if you are familiar with the material; there are also longer ways that are correct. 

• 5 constructions -  the key things that I am looking for is whether you understand the nature of the problem, the general outline of the solution, and any special situations that you have to treat.  

NOTE: While you will have a week to look at the questions and prepare your answers, it would be a good idea to start to study now. The questions are not hard -- if you 1) know where to look and 2) understand what you read. Keep in mind that you will be studying for other tests, so prepare now. If you are not prepared, it will show. If you can't attend class on May 3, LET ME KNOW IN ADVANCE. 

The week of April 19, we will do chapter 25. The major focus will we on Computable Functions, Church's Thesis, and TM's as language generators after we do some practice problems; if we don't finish ch 25, we will the week of April 26. 

The week of April 26, we will review for the final and at the end of the class I will hand out the questions for the final.

The final will be cumulative (but focus mainly on ch 16-25)  in that it will ask you to make connections among the things that you have learned. The problems on the final will tend to require shorter answers than the mid-term but require more thinking. Many of the problems come from the problems at the end of the chapter. Most of the questions are in the form of proofs or explanations similar to the proofs and explanations we have done with the theorems in the book (we have done 70+ to date).  I will give you  8-9 questions at the END of the class on April 26.  You will have a week to prepare to answers to the questions ON YOUR OWN. On May 3, I will select one question for each person at random to answer orally in class with whatever notes you have. You can use the computer and board if you need to. You will have about 10 minutes to answer the question.  (If I see that you know what you are doing, I won't have you go through the whole problem; if you don't know what you are doing, I will ask some questions to prompt you.)  This will give you a chance to prepare your answers yet explain them in your own words and share what you found with others in the class. The grade will depend on the difficulty of the question, how well you answer it and how well you handle follow-up questions. The questions are about equal in difficulty. It will also allow me to ask you follow up questions if your answers are not clear or if you seem to be reading your notes without understanding what you are saying.. I may also want to have you do one or two written answers in a close book part of the test. 

SUGGESTION: GET A DECK OF CARDS AND WORK OUT SOME OF THESE PROBLEMS.

Project 2. will be due 3/29/2000 [This is the same question as #9 on the midterm.] and  project 3 will be due at the end of the semester. The projects are 40% of your final grade with the mid-term and final being 20% each. 

I've added some notes for chapters 19-25 along with cross references. Some of them are sketchy because you really need to look at the diagrams in the text instead.  This part has many more things to follow, so it is important that you keep up. At first, it may seem hard, but as you do all the chapters, the connections fall into place.  Keep in mind that as we prove things, we can use the results without having to do all the work over again. So at the beginning, we will make sure our foundation is solid and then the later parts will be easier.

Perhaps the most important thing one can learn from this course is if we have a working model and we can convert other problems to fit that model, the second problem becomes solvable. This means that we show that one problem in a class can be solved and then show that other problems are in that class and hence can be solved. 

After the break, we have 6 class and 7 chapters on Turing Theory to cover. We will be going a bit slower as Turing Machines are more complicated and the last part of this book ties in all the other concepts. We may skip abound a bit to look for connections. (This is a nice example of a Turing Machine simulator that covers the examples in ch 19.) It will also give us a chance to review as well as look at some implications of Turing machines that are not in the book (such as NP problems). The final will have a project involving Turing Machines. 

The basic outline with the Turing machine section is

•  to show how a TM works (ch 19)

•  show how a Post machine works and prove than PM=TM(ch 20) This combines 19 & 20

•  show how a two PA stacks can be used to simulate a TM (ch 21). This combines 19 & 20 &21

•  look at some variations on TM's (ch 22) This is an extension of 19/20/21.

•  look at the language define by TM's (ch 23) This is an extension of ch 19

•  look at the entire Chomsky Hierarchy (ch 24) this is an extension of ch 19.

•  and lastly define a computer(ch 25).  

You should also start to work on project 1. (Hint: Look at ch. 10 in your discrete structures book. I have a handout from the text that may be of help, but read over the section in the Discrete Structures text which is in the Coach House if you get stuck.) The due date is 3/1/2000.  project 2. will be due 3/29/2000 and  project 3. will be due at the end of the semester. You may work on the project in small groups as long as everyone's name is on it. The last project will be on Turing machines an will be part of your final exam. 

  List of Hints and other notes from the Univ. of Florida. To get an idea of what other  Theory of Computing courses are doing, check out these links.There are a lot of good WEB pages and notes [THIS SITE HAS ENTIRE LECTURES IN POWERPOINT.] out there as well as sample exams. The same hold true for CFG and PDA. The more we do, the more familiar we become and the less work we have to do once we can build on what we know.  

If you have an e-mail other that a WPUNJ e-mail (username@studentent.wpunj.edu) as your primary email address, send me an e-mail so that in the event of poor weather I can get in touch with you.

Previous notes here have been migrated to the notes section. Next week I will rotate the times below to notes as well.

I am aware that the material, to put it mildly, can be very abstract and confusing (and boring at times) and perhaps we are going to fast.. So, if you have any questions as you look over the material, e-mail me or give me a call. If we need to go back to clarify a point, let me know. You should also start to work on project 1. Usually when I leave class, I think about a lot of things that I would have questions about. I listed a few answers below and I may add to them during the week. If you have any questions, let me know.

In the event of snow, we will conduct class via the WEB and e-mail during the week. You may want to look at computer weather models (weather modeling is a good example of computer modeling), the Eastern-Passaic county weather. or local radar. There are some Java based simulations as well as graphical outputs of various model parameters at Air Resources Lab. The basic underlying method used in these models is a  very large (about 1 point every 25 miles over the US at up to 45 levels depending on the model) finite state machine. The basis for numerical weather forecasting began in the 50's with a transition matrix which could be run the the computers of that day.  The main enhancement that has been made is the use of parallel processing,  faster algorithms, higher speed computers (Cray's) and better models.   

Notes
Assignments and Programming Projects
BACKGROUND OF INSTRUCTOR

Just about all of the material in the text is 30+ years old. While the text does a rather good job of presenting the topic, there is no mention of current topics in CS. One of the areas that we will explore from time to time is to see how some of the topics can be used in such areas as compiler construction, grammar checkers, operating systems,  programming languages, computer modeling,  neural networks, artificial intelligence, parallel processing, NP-complete problems and other such areas.

Summary of my notes on Languages and Grammar from Discrete Structures Course (ch 10)  This gives a quick overview of some of the various topics that we will be covering. Make sure that you review trees, stacks and graphs from your previous courses or look at my Discrete Structure notes.

• Since this is a Senior Level Computer Course, there are a number of expectations that I have:

  • Familiarity with Data and Discrete Structures, Windows, MS Office and C++ .

  • Assignments will be read prior to class. By this I mean that you should be familiar with the definitions, diagrams and concepts presented in the chapter and be able to discuss / raise questions in class. You may not understand everything that you read, but you should make an effort to be familiar with the material. 

  •  That if there is something that is not clear, you will ask questions. If you e-mail me before class, I can either get back to you or spend time in class addressing the issue.

  • As there are many examples in your text, we will not be going over every example; we will be doing some representative examples in class, but you are expected to to the rest on your own.

  • As for homework, do as many problems at the end of the chapter as you need to do to feel comfortable that you understand the concepts of the chapter.  

• I will try to address any questions that you have:

  • If the question is of general interest and can be addressed in class, I will include it in the class discussion. Otherwise, I will post it to the WEB. 

  • If the question requires that I do some additional research, I will either answer it during the next class or via the WEB.

  • If the question is of interest to only a few people, I'll either address it after class or via the WEB/e-mail.

  • If questions require longer explanations or if there are a number of questions in a particular area, I may want to group them together and address them in the next meeting.

  • If I need to correct or expand on something covered in class, I will post it to the WEB. 

• Since this course is not a pre-req. for another course and since the subject matter is evolving, we may choose to spend more or less time on some topics or spend some time addressing additional topics. 
  

Deadlines to Drop Course

1/14/2000             100% refund

2/15/2000            50% refund

2/29/2000  last day to drop class

Texts  

The bibliography contains additional titles that may be of interest.

---

Course Information                              

Course Description:

Course Description: This course investigates formal machine models of computation, formal languages, and computability. This includes finite state automata, pushdown automata, Turing machines, languages, and grammars and how they are useful within Computer Science.

Course Objectives:

VII. Course Objectives: 1. To understand the historical and philosophical importance of the questions and results in Theory of Computation. 2. To understand the formal machine models created to investigate the limits of computation. 3. To understand the applications of the formal models and results to other areas of Computer Science.

Course Contents:

1. Review of Mathematical Foundations 2. Grammars a. Regular grammars b. Context-free grammars c. Context-sensitive grammars d. Chomsky Hierarchy of grammars 3. Regular languages a. Regular expressions b. Pumping Lemma 4. Finite automata a. Transition graphs b. Kleene's Theorem c. Non-determinism d. Output - equivalency of Moore and Mealy Machines e. Decidability 5. Context-free languages 6. Pushdown automata a. Deterministic and non-deterministic b. Equivalency c. Decidability 7. Turing Machines a. Recursive and recursively enumerable languages b. Other formulations of computability c. Church's Thesis d. Decidability

Teaching Methods: Classroom lectures, discussions, and problem-solving session. Homework. Readings form outside sources.

Evaluation:      1.   Mid-term and final examination. (20% / 20%)      2.   Programming projects (40%)      3.   Homework assignments.      4.   Class Discussion (20%) There will be at least 3 computer programs: The first project involves an automated toll booth. While simple, it illustrates an actual finite-state machine. The second project takes a definition of part of a programming language and asks you to determine if a given string falls under that definition. This is a simplified version of a syntax checker. The third project is an extension on the second project in that you will be parsing an expression, determining if it is valid, converting it from the conventional infix notation to either postfix or prefix and then evaluating the expression. This is a very simple example of how a compiler translates an expression into machine language and how a machine language program evaluates an expression.  An additional project involving Turing machine will be assigned later either as a 4th project or as part of the Final.

---

ATTENDANCE:

Since each section builds on the previous section, regular attendance is required. Attendance is taken daily. 3 absences will result in a grade of "F" at the discretion of the instructor. Your computer disks, textbook, homework and notes are an integral part of your attendance and class participation. Not being prepared for class will result in a lost of your class grade for the day (an absence).  Game playing, non-class related discussions or other disruptive behavior will result in lost of class participation grade (an absence) for that day.

GRADING:

There will be a mid-term and a final each worth 20%. 30% of your grade will be based on your participation in class discussions in which you are expected to relate your experiences in such areas as working with data, assigned projects and your observations of the material covered in class. 30% of the grade will be a project.

If there are extenuating circumstances for absences or handing in assignments late, the reason should be submitted in a well written formal E-mail message as soon as is feasible.

Requests for extensions should be made via E-mail prior to the due date outlining the reasons for the extension and including what work has been done thus far. In addition to writing practice, this will provide you with the communications skills needed in today's business world by having you present your concerns and requests in writing. As in any business situation, how you state your case will have an effect on whether or not your request will be granted. As in business, there will be times when you need to call because of time constraints and then follow up in writing. Verbal request must be followed up in writing.

 

If there are any problems with getting an assignment done or any other complications during the semester, feel free to either see me before class or call me. I work full-time as a programmer in College Hall and I am in from 6:30am until 3:00pm and I am logged on constantly.

---

   

GRADES

C good understanding of material in the Basic Sections. B solid grasp of material in the Basic Sections and a fair grasp of the material in the Advanced Section. A solid grasp of material in the Basic section along with a good understanding of the material in the Advanced section and Related Sections. D fair understanding of the material in the Basic Section. F inadequate understanding of material in the Basic Section. Plagiarized assignments, handing in work done for another class, 3 or more absences, failure to turn in work, copying assignments (including journals, cheating or any other violation of the Academic Integrity Policy (see attached or Student Handbook pp. 28-30).

  

READ CAREFULLY
 

Plagiarism is trying to pass off someone else's work as your own without proper citation. This includes not only paraphrasing material from outside sources without citation but also includes using programs and work from your sources without citations. It includes taking ideas from sources without attribution (including a classmate's work). It also includes copying from your source by changing a few items here and there.  In all respects, your work should be your own voice except where you have indicated that you have incorporated ideas from others. Remember, it is not improper to use outside sources-- in fact it is frequently a good idea to do so-- as long as you clearly indicate what are your ideas and what are the ideas of others.  If you work with a classmate on a work, put both your names on both papers to indicate the collaboration. If only part of the work was worked on jointly, then cite those parts. Not only is this the correct thing to do, but it avoids the problem of who was/were the original writer(s) when, by sharing ideas, you come up with a work that is similar to someone else's. In any event, both works/programs should be distinct with each writer contributing his or her own ideas. (i.e.. if two people are working on an assignment, the ideas may be similar, but the papers should be written by each person.) Work which is in whole or substantially identical will both receive an "F" since it is plagiarized unless there is proper citations.  If you are unsure about what constitutes plagiarism or what you need to avoid it, make sure you ask or put a note on your work.  Why is plagiarism frowned upon? The reason is that you are submitting work that was done by others and handing it in to be graded as you own work. In addition, it is not fair to the people that do their own work. The minimum penalty is an F on the paper. Subsequent violations may result in an "F" for the course. (See Student Handbook for College policy.)

You are the visitor to this site.

 
 HTML  PDF