It is difficult to succeed in CS 154 without obtaining the class text and reading the material that's relevant to each day's class.
If you think that you cannot afford to buy the text, I strongly recommend that you become familiar with the library course reserves (described below). You should also consider buying a used copy, or a paperback copy, and reselling it at the end of the semester. One major reason I chose the Hopcroft, Motwani and Ullman text is that I expect it to be in use for many years (so copies of the text will be easy to resell). Of course if you intend to resell your textbook, you shouldn't make notes or drawings in it.
Unfortunately, most of the exercises in HMU (and most other textbooks) are not particularly helpful to the average student. They are also often quite time consuming and peripheral to the main topics of the course. Usually it's only the first couple of exercises of a section that are both easy and useful. The class web site gives a list of exercises for the HMU text that I think are the most helpful.
The textbook's web site is useful in several ways. It provides an alternate source of class notes, transparencies, and exercises, a list of errors in the text, and solutions to those exercises that are starred in the text.
A surprising number of students do not look at solutions provided to the problems they were asked to solve on tests and problem sets. It is a very good exercise for you to see if you can get the answers that I provide for these problems, if you didn't get them right the first time. I am always happy to explain where these solutions come from, when it's not clear from the discussions in class.
The SJSU library maintains a course reserve area where instructors may place material for student checkout. I use the course reserves fairly heavily. For courses like 154 where students may find some textbooks helpful but not others, I try to maintain a good selection of alternative texts (as well as the required course text).
Course reserve material may be checked out at the south end of the first floor circulation desk. Most material in my course reserves may be checked out for only two hours. This is enough time to read a section of the text and perhaps make some photocopies. It's also enough time to bring the text to class, if you return it promptly.
You should look at the texts available in the 154 course reserves. Most of these texts cover very much the same material as our text. You may find a text that is more helpful to you than the required course text. If nothing else, these texts will have different examples than the HMU text, and many will have more examples than the HMU text does.
One warning, however: most texts use a slightly different notation that ours does. This is of some importance since the course depends quite heavily on notation. It's not difficult to translate the notation from one text to another, but it's difficult to keep straight the notation for several different texts. So you might want to settle early on a text (or two) that you like, and stick with it (or them).
The class web site has a number of links that should be useful. For example, the transparencies that are presented in class each day are available there. It might help you to look at them before class, and to make sure that you have them available during class. If you bring to class a laptop equipped for wireless use, you can find them on the web site during class. This is particularly helpful if you want to consult a transparency that is not the one that I am current presenting.
If you don't want to bring a laptop, or if you prefer hard copies, you can print the transparencies before class. Hard copies may also be useful during exams, when the use of notes but not the use of computers is permitted.
I do post solutions to the problem sets on the class web site after I grade them. Occasionally I will provide notes on the problem sets that are distinct from the solutions. You can look at the problem sets and solutions and any notes for past semesters by checking the web sites for old CS 154 classes. These web sites are available directly from this page and also from my home page by following the link labeled
Don't forget that you are responsible for the information on the handout on assignments that was distributed on the first day of class. This handout is available from the class web site.
Very few students succeed in CS 154 without coming to class regularly and taking notes. The transparencies available on the class web site should be helpful, but they are no substitute for the notes that you take in class. In theory it is possible to learn the course material directly from the text, but most students (of any instructor) profit greatly from the additional insights provided in lectures.
Although there are very few concepts that I cover in class that aren't covered in the text, some of these concepts are presented quite quickly in the text. So a large part of what I do in class is spend time motivating and explaining them. Another large part of what I do in class is to present additional examples. There will be a couple of cases where I will present different (and I think, clearer) algorithms or constructions than the text does. And of course I do answer questions in class. You will miss all of this assistance if you don't attend class.
There are undoubtedly many web-based resources that will help you to better understand the material of the class. I will provide links to a few of them from the class web site by the first or second week of the class. Since I have a limited amount of time to search for such sites, I'm interested in hearing about any other such sites that you find especially useful.
There is no substitute for reading the text. The purpose of the lectures is to assist you in reading and understanding the text -- not to be a substitute for the text. The same applies to the transparencies presented in class, and to any of the other resources listed above.
The examples that I go over in the lectures are intended to supplement the examples in the text. They are not intended to be a substitute for them. There's no substitute for reading and understanding the examples in the text.
I was always one of those students who preferred to attend the lecture on a given topic before reading the textbook's coverage of that topic. So I don't assume that my students have read the textbook before the lecture. However if you are a student who prefers to read the textbook before attending the corresponding lecture, you should continue to do that in this class. Hopefully you know by now which kind of student you are. In either case, you should read the text at some point.
As mentioned above, you might want to refer to other texts, such as those available in the course reserves for CS 154.
It will be helpful to arrange before class to have in-class access to the transparencies that will be presented that day. This will allow you to consult transparencies other than the one currently being presented. If you don't plan on bringing a laptop to class, you will need to arrange to get hard copies. Again, although going over the transparencies can be helpful, reading the transparencies is not a substitute for reading the text.
A very good way to see whether you understand the material of the course is to see whether you can trace the behavior of the many algorithms of the course on sample input. I certainly rely on this observation when I construct tests. So you should be familiar enough with these algorithms that you can trace their behavior quickly during a test.
For most of these algorithms, it's relatively easy to construct your own sample input. In some cases, you can even check your output. For example, after constructing a regular expression that's equivalent to a given DFA, you can construct another DFA from the regular expression and check whether the two DFAs are equivalent.
In many other cases the algorithm will be a construction algorithm whose output is supposed to be an automaton or grammar with a certain property. If you have time, it's wise to do some testing of the automaton or grammar that you have constructed to see whether it has the appropriate property. Normally you will know something about which strings should be accepted, so you can do some testing by feeding it input strings and seeing whether they are accepted. Naturally you should test some strings that should be accepted, and some that shouldn't be. With luck, you'll also be able to look at your output structure and determine some of its properties (e.g., that it only accepts strings ending in 0).
Much of the confusion that students have about the material of the course takes the form of type errors. These errors are just as fundamental as they are in programming, where they prevent a program from compiling. The good news is that they are about as easy to deal with -- if you're careful.
For example, sets should be distinguished from their members. This may sound obvious, but it's fairly common for students to use the term "alphabet" to mean a single symbol rather than a set of symbols, which is how it's defined. Also, when we talk about a language being finite, we mean that it is a finite set of strings, since a language is defined as a set of strings. We don't mean that the strings are finite (in fact, we never really deal with infinite strings in this class).
But note that a "set of strings of finite length" refers to a set of strings, none of which is infinite. Such a set may be infinite. On the other hand, a "set of strings of bounded length" means that there is an integer M such that none of the strings has length greater than M. If all the strings are strings over the same finite alphabet, such a set must be finite.
As another example, numbers should be distinguished from strings of digits. As still another example, a string of length 1 should be distinguished from its first (and only) symbol.
The concept of ambiguity is important in this class, and you will eventually need to know that it is a property of grammars, and not of languages. In other words, languages cannot be ambiguous. It's possible that every grammar for a language may be ambiguous, in which case we call the language inherently ambiguous. So inherent ambiguity is a property of languages and not of grammars.
Another possible source of confusion comes from an important class of functions called transition functions (which are typically named δ). In some cases the values of these functions are sets, and in some cases they are not. It's important to know which case you're dealing with. When they are sets, you don't want to say that a particular δ function will have two different sets as values, for the same input. Again, this may seem obvious, but it's easy to forget in the middle of a complex computation.
Some of our terms will be overloaded, which can cause confusion if you forget this. For example, concatenation of two strings will produce another string, while two languages can also be concatenated to produce another language.
Also, in some cases it is convenient and thus common for authors to abuse notation by deliberately making type errors. The box on page 87 of HMU gives one example. HMU suggest that it is common for authors to provide an expression as an argument to a function that is technically defined only on languages. In a sense, a sort of coercion happens in these cases -- for any (regular) expression E there is a corresponding language L(E), and it is L(E) to which the function is applied.
As another example, some authors use the name δ both for a transition function defined for single symbols, and for a transition function defined on entire strings. The HMU text uses a separate notation in this latter case.
One common family of errors has to do with misuse of the the notation for progress in a computation. The infix operator |- is used to separate steps of a computation; it roughly means that the configuration to the right can be derived from the configuration to the left in a single step. The infix operator => has a roughly similar meaning, but is used when parsing. The symbol -> should not be used in either case, but it should be used when specifying grammars.
In general, you should be aware of the notational conventions used in the text (and in any other text that you consult). Many of the notational conventions of the HMU text are given in boxes on pages 178, 232, and 335.
You should of course understand the difference between different operations on the same type. For example, you should be comfortable with the difference between union of languages and concatenation of langauges.
Finally, an all-too-common type of error has to do with constructions. We observed above that many of the algorithms covered in class will construct a grammar or automaton with a particular property. Often it's easy to see by inspection (that is, without using the algorithm) what object should be constructed in simple cases. Where students go wrong is in trying to construct the correct object by inspection in more complicated cases. It's safest, if not always quickest, to use the algorithm for these constructions in all cases. In fact, in some cases I will ask you to use a particular algorithm for the construction. Watch out for these cases, since I will have to penalize you fairly severely if you don't use the required algorithm.
Two important concepts that appear in some form or other throughout the course are the notions of breadth-first search and of a finite description. All of our ways of describing langauges, whether by grammars, by automata, by regular expressions, by algorithm, or simply by listing their elements (if they are finite languages) are finite descriptions. In particular, no algorithm can determine membership in a language that has no finite description.
Typically in CS 154 we use breadth-first search to find a complete solution to a problem from among a set of partial solutions. Here we assume that each partial solution, including the empty partial solution where we begin looking, is linked to a finite number of somewhat more complete partial solutions.
Unlike many CS courses, grades on the tests and assignments for CS 154 don't really decrease as the class goes on. Later material isn't completely dependent on earlier material. And though the objects that we study later are more complicated than those we study at first, you aren't expected to know as much about the later ones as the earlier ones. In addition, as we cover more classes of objects, part of what you need to know is how the behavior of one class differs from the behavior of another. This is largely just a summary of earlier knowledge, so it's not particularly hard to learn.
The tests in this class are generally less abstract than the problem sets -- if only because you have less time to do them. So don't be discouraged if you don't do well on the first problem set. You may find the tests easier.
Remember that I do sometimes adjust grades upward for people who have been improving through the course, and for people with one bad grade. And, as observed above, it's not as hard to improve your score in CS 154 as it is in some other CS classes.
Return to CS 154 Home Page