CSC 317: Automata Theory and Computability 2015-2016 Sesssion

Teaching Team

1. Dr. (Mrs.) R. A. IYANDA

2. ''Tunji  ODEJOBI (Course Coordinator)


PLEASE NOTE THAT THIS COURSE HAS BEEN MOVED TO Moodle. Click on E-Learning Support to reach CSC 317 Moodle

Introduction

This course comprises two components: (i) Automata theory and (ii) Computability. In the Automata aspect of the course we will discuss issues in the design of abstract machines. Specifically we will look into how tools developed around the theory of discrete mathematics can be used to formally describe and explore alternative solutions to computational problems. In the computability aspect of the course, we will look into a way of determining whether a problem can or cannot be solved computational. As for the problems that can be solved computationally, we will also consider the cost (space and time) of implementing the solution. We will also see that languages and their associated grammars are very powerful mechanisms for computational problem description and solution.

This course is central to computing in general since it treats most of the important concepts that underlies computer science and engineering. Many of the tools used in the design of computer hardware  (e.g. logic circuits) and the development of software (e.g. programming language compilers) have foundation in Automata theory and computability.

Learning outcomes

At the end of this course, students are expected to have gained knowledge that, with  practices and exposure, will culminate in the understanding of the processes involved in the formal description of computational problems and the development of abstract machines for their solution. The underlying aim is to impact on students the principles and theoretical foundations that is essential for future studies into computing and formal systems development. Specifically, students are expected to gain understanding in the following:

  • Precise problem specification and solution requirement statement;
  • Design of accurate and provable solution;
  • Analysis of the limits and extents of possible solution(s);
  • Possible applications of solution and the strategies for their implementation.

Software

The following software will be used in the practical aspects of this course. Students are expected to Download and Install the software for personal use only.

  • Visual Automata Simulator - A tool for simulating, visualizing and transforming finite state automata and Turing Machines (c) 2004-2006 Jean Bovet
  • JFLAP - A software for experimenting with formal languages topics including non-deterministic finite automata, non-deterministic pushdown automata, multi-tape Turing machines, several types of grammars, parsing, and L-systems.

Please, download the course description here.

NEW: Please download the Laboratoy grouping

Please Download LAB ONE EXPERIMENT description here

Practical Schedule [Please Contact Dr.(Mrs.) Iyanda for more information]

Group 1 to 6 - Tuesday  10am to 1pm

Group 7 to 12 - Wednesday  10am to 1pm

Each group is expected to come to the laboratory with their laptops with JFLAP installed. The practical will hold at the Digital Computer Laboratory (RM 006) [Changes to this, if any,  will ne announced in the Class].