JOIN HERE

# COS2601

You are here: Main Page > Unisa Modules > Computer Science > COS2601

Online Dating in South Africa

## 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

1. Background
2. Languages
3. Recursive Definitions
4. Regular Expressions
5. Finite Automata
6. Transition Graphs
7. Kleene's Theorem
8. Finite Automata with Output
9. Regular Languages
10. Nonregular Languages
11. Decidability

## The COS2601 textbook

### Prescribed textbook

 ISBN 9780471137726 Title: Introduction to Computer Theory Author: Daniel I. A. Cohen Edition: 2nd Publisher: John Wiley and Sons Year published: 1996 Year prescribed: 2010

### 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)


## 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 $\left\{a, b\right\}$
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 $P$ 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 $FA_1$ and $FA_2$ ($r_1 + r_2$)
• 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 $a^{n}a^{n+1}b^{n}b^{n-2}bb$ 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 $a^{2n}b^{n}$ is not regular.
• Question 2:
Given the alphabet $\left\{a, b\right\}$
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 $P$ 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 $FA_1$ and $FA_2$ ($r_1r_2$)
• 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 $\left\{a, b\right\}$, 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 $S*$ over the alphabet $\left\{a, b\right\}$ that do not end on $ba$.
b) Give the set $S$ and $T$ where $S* \cup T* \not= (S \cup T)$
• 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 $\left\{a, b\right\}$
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 $P$ of all positive integers greater than or equal to 5,
b) formulate the induction principle,
c) apply the induction principle to prove that $2n-3 \leq 2^{n-2}$
• Question 4:
a) Give a regular expression which defines the language which generate all words with the total amount of $a's$ divisible by 3.
b) Give a regular expression which defines the language which generate all words ending on $ba$.
• Question 5:
Build an FA that does not accept the substring $ab$ 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:
$FA_1$ and $FA_2$ 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 $a^na^{20}b^{20}b^{n+2}$ is non regular.
• Question 10:
Explain briefly the method of finding if a language is accepted by two FA's, $FA_1$ and $FA_2$.

The exam in Oct/Nov 2008

The exam was very similar to those of previous years. The inductive proof required you to show that $x-y$ is a divisor of $x^n-y^n$ for all positive integers $n$.

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!

• 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

Bronwen Solutions to chapter 4 2003 A student's (correct) worked-out solutions to the first 11 problems in chapter 4 of the textbook by Cohen.
Bronwen Solutions to chapter 2 2003 A student's (correct) worked-out solutions to all 20 problems in chapter 2 of the textbook by Cohen.