Chapters Covered in Prescribed Book The following are the chapter headings for the subject, which should give you an idea of what is covered in this subject…
Chap 2 – Languages Chap 3 – Recursive Definitions Chap 4 – Regular Expressions Chap 5 – Finite Automata Chap 6 – Transition Graphs Chap 7 – Kleene’s Theorem Chap 8 – Finite Automata with Output Chap 9 – Regular Expressions Chap 10 – Nonregular Languages Important Sections outlined by the Examiner The following was taken from the notes of the lecturers for preparation for the COS201 exam as things we should make special note of.
Understanding and analysis of different languages over the alphabet {a, b} and the application of the Kleene closure. (p.g. 14 – 18 of TB, and 128 of TB) Induction (discussed in depth in the study guide). Recursion (recursive definitions of regular languages are discussed in detail in the study guide). Regular expressions: you should be able to provide a regular expression for a required language and to analyse a regular expression in order to determine the language generated. Machines: FA’s (Finite Automata), TG’s (Transition Graphs), NFA’s (Non-deterministic Finite Automata), Mealy machines, and Moore machines - you should be able to draw a required machine and to analyse a provided machine in order to determine which language is being accepted by the machine in question, or to determine the output in the case of a Mealy or a Moore machine. You should also be able to convert a Mealy machine to a Moore machine and vice versa. All the algorithms inside Kleene’s theorem are of utmost importance. Chapter 7 should be studied in detail. You should be able to determine the intersection of two regular languages by applying the algorithm as described in Chapter 9 of Cohen. The application of the Pumping Lemma with length as described in the study guide is important. The application of the blue paint algorithm should be studied.
