CS 6041: Theory of Computation - DFA Algorithm Design and Analysis

This document presents a solution to the CS 6041 Theory of Computation term project, focusing on the design, analysis, and implementation of algorithms using Deterministic Finite Automata (DFA) models. The project involves reviewing a problem involving three species on a planet and extending it with a parameter N representing the number of individuals. Students are tasked with developing an efficient (polynomial) algorithm to produce expected DFAs for a given N (0-20), analyzing its efficiency, implementing it in a chosen programming language (with options for symmetric or non-symmetric representations and output as directed graphs or state tables), and answering questions about MUST-FAIL, MIGHT-FAIL, and CAN'T-FAIL states, as well as identifying any nondeterministic states. The project is broken down into tasks with specific point allocations and assessment criteria, including a final report and a class live demo, both of which are graded based on the correctness of the algorithm, analysis, and implementation, as well as the clarity of the presentation and the answers provided.

CS 6041 – Theory of Computation
Fall 2016
Term Project: Design, analysis and implementation of algorithms
using DFA models.
Version 0.9 – (this will become the final version AFTER receiving
suggestions from students)
Total Points: 300 point (or 30%)
In this term project, students (either a team of two; or individually) will review and
implement the finite automaton of “strange planet” discussed in class, originally
developed by Jay Misra.
First, review the description of this problem in lecture slides (slide 10 – slide 23) in
“Finite Automata – Motivation by Example” (i.e., the first lecture material).
On a distant planet, there are three species {a, b, c}. The rules are: (R1) any two
different species mate, (R2) if they do, the participants die, but (R3) the two
children of the third species are born.
The planet fails if at some point of time all individuals are of the same species.
For the definition of a state and an event (i.e., “a-event”, “b-event”, “c-event”), we
will use the same definitions as discussed in class or given in the related slides.
Also, students can use the same terminologies for “MUST-FAIL”, “MIGHT-
FAIL”, and “CAN’T-FAIL” as discussed in class.
After you review the scenarios and think about interesting questions using the
scenarios, we need to extend the original problem using the following
parameters:
N: the number of individuals in the planet (N = 0, 1, …., 20)
The following four tasks must be complete.
Task 1: Develop an efficient (i.e., polynomial) algorithm to produce the expected
DFAs for a given value of N (N = 0, 1, …, 20).
Task 2: Analyze your algorithm and prove that your algorithm is efficient (i.e.,
polynomial).
1

Task 3: Implement your algorithm using your choice of programming language.
Your implementation can be done with either symmetric or non-symmetric
representations. Your output of DFA(s) can be represented in a form of either
directed graphs or state tables.
Task 4: As part of developing an algorithm and of implementing it, the following
questions should be answered, as well.
1. For each value of N, find all “MUST-FAIL” , “MIGHT-FAIL”, “CAN’T-
FAIL” states.
2. For each value of N, does the resulting DFA(s) contain any
“nondeterministic” state? If so, identify it/them.
These tasks above (T1 – T4) are the minimum requirement.
For extra points, students can further explore either more general or other
interesting problems, which can be proposed and then consulted with the
instructor. If so, this should be done in advance (at least by end of Week 8).
Choose a team wisely, if so; it is your full responsibility of making a team and
finish this work until the end. So, the spirit of team-work is needed (no excuse.)
Point Breakdown: In terms of quality of the work
 Task 1 [30%]: Correctness of algorithm
 Task 2 [10%]: Correct analysis of algorithm
 Task 3 [30%]: Correct implementation
 Task 4 [30%]: Correct answers
In terms of dissemination of the work:
 Final Report [100 points]: Either MS Word format or PDF is preferred. No
more than 10 pages, including the captured test runs.
o Description of algorithm
o Analysis of algorithm
o Source code with comments
o Execution output/result (inc., the captured output)
2

Assessment 1 [100]: Final Report is to be submitted to the instructor for grading.
 Class Live Demo [200 points]: Either PPTs or other reasonable forms for class
demo.
o Correctness of Task 1 – Task 4: 100 points
o Class demo & Q/A: 100 points
Assessment 2 [200]: For class demo, classmates will perform the assessment.
The detailed rubrics for Class Demo should be distributed by the instructor at least
two weeks prior to the Demo Week/Day.
- The End -
3