The University of Western Ontario
Department of Computer Science

CS 9870b: Automata and Implementation

Course Information -- Spring 2011

Description

In recent years, more and more new applications of automata and formal language theory have come to light in computer software and other areas of computer science. The new applications raise new questions in automata and formal language theory, especially questions related to efficient implementations of automata, regular expressions, and grammars.

This course will focus on the topics of implementing automata and formal language objects. In the course, we will first review and study the basic theory that is essential to many algorithms in this area. Then we will study some most recent results published in international workshops, conferences, and journals. Future directions in this area of research are also discussed. Participants of the course are expected to give presentations of recent results in this area.

Prerequisites

CS331 Foundations of Computer Science I or equivalent
CS340 Analysis of Algorithms or equivalent

Topics

  • The Myhill-Nerode theorem and minimization of finite automata
  • The similarity relation and minimal cover automata for finite languages
  • Alternating finite automata and their bitwise implementation
  • Practical regular expressions and their properties
  • Most Recent results on State complexity
  • Future directions in automata implementation

Instructor

Professor Sheng Yu, MC374, syu@csd.uwo.ca, Ext. 83715

Office hours

Thursday 11:30-1:30

Class meeting time and place

3:30-5:30 Wednesday, MC 316

Textbook

No textbook is specified for the course.
References will be specified in class.

Assignments/exams/seminars

  • Each student is required to give a seminar in class. The duration of the seminar depends on the number of students registered for the course.
  • There are several assignments given by the instructors during the term.
  • No tests or exams.

Evaluation

The final mark is given according to the following factors:

  • Seminar 50%
  • Assignments 30%
  • Participation 20%