CS 6041 – Theory of Computation | DFA Model Assignment
Added on 2019-09-30
3 Pages787 Words304 Views
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
End of preview
Want to access all the pages? Upload your documents or become a member.