CSC 17 Lab: Finite State Machines DNA sequences are represented using the symbols A, C, G and T. As part of a multi-million dollar research project, a group of geneticists collected numerous DNA samples from tigers, lions, panthers, and other members of the feline family. After years of analysis they have announced a shocking discovery. All their DNA samples contained a certain pattern: a number of C's, followed by the SAME number of A's, followed by the SAME number of T's. For example, small felines had sequences like CCCAAATTT, while larger ones (lions and tigers) contained DNA that looked more like CCCCCCCCCCCCCCCCCCCCCCCCAAAAAAAAAAAAAAAAAAAAAAAATTTTTTTTTTTTTTTTTTTTTTTT. To confirm their incredible finding, they need you to write a program to detect the presence of this pattern. Whether or not yo believe in their finding is besides the point. Study the abstract class FSM4 that implements an abstract finite state machine (FSM4.java) and the sample machine that recognizes a(a|b)*b (in dfa4.java). Then implement an appropriate state machine as a subclass of FSM4. Use the state transition diagram that I gave you as a guide, but you need to think carefully also. As always... YOUR ARE NOT ALLOWED TO CHANGE ANYTHING IN THE FSM4 ABSTRACT SUPERCLASS. Note that the machine detects embedded patterns, and reports the position and size of the pattern. Your program must ultimately print the same information as mine: $ java cat2 ATGCCCAATTTT pattern detected at position 4, size 6 $ java cat2 CCAAATTT pattern not detected PLEASE NOTE THAT THER ARE 4 POSSIBLE INPUTS: A, C, T AND G. Although G does not appear in the pattern (dogs have G, but not cats), it is a possible input that must be recognized: usually it will cause the machine to return to the start state (after resetting all counters). *** For this machine, you should set keeprunning to false so that it it returns true as soon as the pattern is detected. Note, given: interface action { int act(); } To create a new instance of action on the fly, you can do, for example: action A = new action() { public int act() { return 1; }}; which is equivalent to the following lambda expressions: action A = () -> { return 1; }; action A = () -> 1; // if the body contains just one return statement. Additional hint: Since the most common 'action' is to reset all counters and go back to state 0, you should define a reset() function to reset all counters, then initialize the action table M to have a default action: for(int i=0;i { reset(); return 0;}; // default action // then set the other actions by overwriting some M[i][k]... //// MEGACHALLENGE: ************************* Modify the state machine, and your program, to find the longest pattern in a string. For example, if the input is: ACATGCCAATTGCCCCCCAAAATTTTC the current machine (as defined by FSM diagram) will stop after the 4th character, and report a pattern of only length 3. But you want to find the longer pattern towards the end of the string. You need to first modify the statemachine (hint: keep going after reaching the accept state, but use actions to record/output whenever the cat pattern has been found.) //// GIGACHALLENGE: ************************* A finite automaton, unlike a finite state machine, cannot use extra memory (such as counters) and actions should not do anything other than to transition to next state, i.e. all actions are of the form ()->nextstate. A "probabilistic automaton" (similar to a "Markov chain") is a finite automaton where, given state s and input i, the machine can transition to several possible next-states, each determined by a probability (a number between 0 and 1). The sum of all the probabilities of possible nextStates MUST add up to 1. Implement probabilistic automaton as a generic (possibly abstract) class and at least one concrete subclass. Such automata are useful in simulations, including games. hint: use a 3D array.