COS2601
From WikiStudent
Contents 
Theoretical computer science 2
Introduction
Theoretical Computer Science 2 is a module that allows you to study a class of theoretical machines known as Finite Automata (FA). These FA's can be used to recognize symbol patterns like binary sequences eg. '10101011100111' or character strings eg. 'abcdefgh'. These sequences or strings are called languages which are fed to these machines and either accepted or rejected.
There are various applications for such theoretical machines in Computer Science. Typical applications are the development of Communications protocols and Cryptography.
The prerequisites for this module are either COS1501 or MAT2612.
COS101S provides a natural introduction to the topics presented here.
There are also similarities with MAT2612 in a few significant areas.
The Unisa syllabus
 Background
 Languages
 Recursive Definitions
 Regular Expressions
 Finite Automata
 Transition Graphs
 Kleene's Theorem
 Finite Automata with Output
 Regular Languages
 Nonregular Languages
 Decidability
The COS2601 textbook
Prescribed textbook

Quotes from the textbook
"...but what is far less clear is exactly what ϕ* should mean. We shall avoid this philosophical crisis by never using this symbolism and avoiding those who do."  Cohen p. 37, Chapter 4 (Regular expressions)
Recommended reading
The COS2601 exam
Past exam papers
The Exam in May 2011
 Question 1
Fairly Simple, Set theory. If you went over your MCQ of Tutorial letter 101, you would've been fine.
 Question 2:
 Given the alphabet
 a) Give the universal set,
 b) the generator(s),
 c) a function on the universal set,
 d) write the definition of the language EVENAB where the words are of even length and which do not contain the substring ab.
 Question 3:
 a) Give the recursive definition of of all positive integers greater than 2,
 b) formulate the induction principle,
 c) apply the induction principle to prove a given equation.
 Question 4:
 You had to decide whether two regular expressions are similar or equivalent, if not you had to supply a counter example.
 Question 5:
 Build an FA that meets certain criteria.
 Question 6:
 Use Kleene's theorem to convert a Transition Graph into a regular expression.
 Question 7:
 Build an FA which is the concatenation of and ()
 Question 8:
 Simplify a given FA with a largish number of states so that it only has 4 states.
 Question 9:
 Use the Pumping Lemma with length to prove that the language is not regular.
 Question 10:
 I've noticed in these questions, they ask you to explain an algorithm or method of proof and then apply it. In this question, it was to decide whether an accepted language was finite or infinite. They are getting clever now, students are just memorising without understanding, thats why they are asking to explain your answer.
The questions closely resembled the supplied example paper from the 2011 and 2009 exam tutorial letters. No Mealy's or Moore's!
The Exam in May 2010
This exam was relatively straightforward. The questions closely resembled the supplied example paper.
 Question 1:
 Use the Pumping Lemma with length to prove that the language is not regular.
 Question 2:
 Given the alphabet
 a) Give the universal set,
 b) the generator(s),
 c) a function on the universal set,
 d) write the definition of the language EVENnotAB where the words are of even length and which do not contain the substring ab.
 Question 3:
 a) Give the recursive definition of of all positive integers greater than 3,
 b) formulate the induction principle,
 c) apply the induction principle to prove a given equation.
 Question 4:
 You had to devise two regular expressions according to certain criteria.
 Question 5:
 Build an FA that meets certain criteria.
 Question 6:
 Use Kleene's theorem to convert a Transition Graph into a regular expression.
 Question 7:
 Build an FA which is the concatenation of and ()
 Question 8:
 Simplify a given FA with a largish number of states so that it only has 4 states.
 Question 9:
 Some questions (mostly theory) about decidability.
 Question 10:
 Given a word and some languages over the alphabet , say whether or not you think it is possible for the word to be in one of the languages.
The exam in Oct/Nov 2009
The 2009 exam was definitely easier than the 2008 exam. The following 10 questions were asked:
 Question 1:
 a) Give the set over the alphabet that do not end on .
 b) Give the set and where
 Question 2:
 Very similar to the assignment question and it was exactly the same as the one in the sample paper that was given.
 Given the alphabet
 a) Give the universal set,
 b) the generator(s),
 c) a function on the universal set,
 d) write the definition of the language ODDAB where the words are of odd length which do not contain the substring ab.
 Question 3:
 Very similar to the assignment question and it was exactly the same as the one in the sample paper that was given.
 a) Give the recursive definition of of all positive integers greater than or equal to 5,
 b) formulate the induction principle,
 c) apply the induction principle to prove that
 Question 4:
 a) Give a regular expression which defines the language which generate all words with the total amount of divisible by 3.
 b) Give a regular expression which defines the language which generate all words ending on .
 Question 5:
 Build an FA that does not accept the substring anywhere in it.
 Question 6:
 Use Kleene's theorem to find a regular expression. Had to convert a TG to a regular expression.
 Question 7:
 and had to be used to find the union of these two FA's.
 Question 8:
 The input and output on a Moore machine was given and the Moore machine was to be drawn using only three states.
 Question 9:
 Had to use the Pumping Lemma with length to prove that is non regular.
 Question 10:
 Explain briefly the method of finding if a language is accepted by two FA's, and .
The exam in Oct/Nov 2008
The exam was very similar to those of previous years. The inductive proof required you to show that is a divisor of for all positive integers .
The exam in Oct/Nov 2007
The exam this year covered most of the syllabus, and the format has not changed over the years. There were enough simpler questions to push 40% and above.
The exam in Oct/Nov 2003
The exam was very nice  and predictable. (The questions were nowhere near as difficult as some of the textbook ones). It seems they keep the format the same every year, and this exam was incredibly similar to the one from 2 years back. At least 25% of the questions came straight from that past paper.
How to pass COS2601
Study tips
 There are 20 exercises at the end of each chapter of the prescribed textbook by Cohen  unfortunately all without solutions. But it doesn't hurt to try them all out anyway. We could buy a (very handy) disk from Unisa with interactive exercises on the pumping lemma. It's well worth buying, even if you don't have any problems. The exercises were well chosen and written to catch you out!
Useful links
 Jflap software  This is a link to excellent software for helping you studying the module and expecially useful for drawing the diagrams. Just double click on the jar file to run the program. With it you can do machines, grammars, lemmas and more (and it's free).
 An outline of outcomes of the subject  Things you should know for the exam.
Study notes
Download notes
Author  Download link  Year created  Description 

Bronwen  Solutions to chapter 4  2003  A student's (correct) workedout solutions to the first 11 problems in chapter 4 of the textbook by Cohen. 
Bronwen  Solutions to chapter 2  2003  A student's (correct) workedout solutions to all 20 problems in chapter 2 of the textbook by Cohen. 
Create notes online
Student opinions
Student survey
Pros of COS2601
 If you work very hard at this module you'll find COS3701 a breeze. The extra hours spent in second year will definitely pay off in final year as the concepts are exactly the same.
Cons of COS2601
 This is a very abstract module which will require a lot of dedicated studying.
 The textbook is almost like a very long piece of cryptic notes the author made while he was busy with his PhD or something. It is difficult to follow and the Unisa study guide is in some instances necessary to decrypt the textbook, but it doesn't succeed in doing that every time.