SDSU Department of Computer Science
  
Home Contact Us Undergraduate Student Info Graduate Student Info Faculty & Staff News & Events
News Calendar Problem of the Fortnight

November 2008 Calendar

CS Masters' Thesis Defense

Title: Computing the Number of Distinct Regular Languages Accepted by k-state NDFAs over a 2-letter alphabet
Speaker: Di Huang
Date: Sunday, November 30, 2008
Time: 5:00 p.m.
Location: GMCS 307
Thesis advisor: William Root

Abstract:
While enumeration problems related to finite automata have been studied for almost fifty years, until very recently such research has addressed almost exclusively the enumeration of various subclasses of automata, rather than enumeration of the distinct regular languages accepted by those automata. This thesis project comprised the development of a C++ program which, given positive integer input k , determines the exact number of distinct regular languages accepted by k-state nondeterministic finite automata over a two-letter alphabet.
webmaster@cs.sdsu.edu page counter College of Sciences