CS 6041 – Theory of Computation | DFA Model Assignment

Added on -2019-09-30

| 3 pages
| 787 words
| 304 views

Trusted by 2+ million users,
1000+ happy students everyday

Showing pages 1 to 1 of 3 pages

CS 6041 – Theory of ComputationFall 2016Term Project: Design, analysis and implementation of algorithmsusing DFA models.Version 0.9 – (this will become the final version AFTER receivingsuggestions from students)Total Points: 300 point (or 30%)In this term project, students (either a team of two; or individually) will review andimplement 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

Found this document preview useful?

You are reading a preview
Upload your documents to download
or
Become a Desklib member to get accesss

Students who viewed this