JOIN HERE


COS2601

From WikiStudent

You are here: Main Page > Unisa Modules > Computer Science > COS2601
Jump to: navigation, search

Online Dating in South Africa

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

  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)

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 LaTeX: \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 LaTeX: 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 LaTeX: FA_1 and LaTeX: FA_2 (LaTeX: 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 LaTeX: 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 LaTeX: a^{2n}b^{n} is not regular.
  • Question 2:
Given the alphabet LaTeX: \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 LaTeX: 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 LaTeX: FA_1 and LaTeX: FA_2 (LaTeX: 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 LaTeX: \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 LaTeX: S* over the alphabet LaTeX: \left\{a, b\right\} that do not end on LaTeX: ba.
b) Give the set LaTeX: S and LaTeX: T where LaTeX: 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 LaTeX: \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 LaTeX: P of all positive integers greater than or equal to 5,
b) formulate the induction principle,
c) apply the induction principle to prove that LaTeX: 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 LaTeX: a's divisible by 3.
b) Give a regular expression which defines the language which generate all words ending on LaTeX: ba.
  • Question 5:
Build an FA that does not accept the substring LaTeX: 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:
LaTeX: FA_1 and LaTeX: 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 LaTeX: 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, LaTeX: FA_1 and LaTeX: 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 LaTeX: x-y is a divisor of LaTeX: x^n-y^n for all positive integers LaTeX: 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!

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

AuthorDownload linkYear createdDescription
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.
       

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.
Personal tools