(r3) CSC122F2022Lab2NFSM < CenterForComputing

Tags: view all tags
---+ Nondeterministic Finite State Machine
<B>This has been changed to be an extra credit for lab 1</b><br><br>
A nondeterministic finite state machine is a finite state machine that allows for the changing of a state with no use of input and/or multiple options for a given state and input.  [[https://www.geeksforgeeks.org/difference-between-dfa-and-nfa/][Geeks for Geeks]] can explain it but the nice thing about this lab is you <b>DON'T</b> need to understand everything in that website.  Your goal is to adapt a solution for the previous program to determine if a given machine is deterministic or not and to run it (in either case) on a given string.
---++ Objectives
   1. Refresh programming skills especially in regards to recursion
   1. Learn more about finite state machines.
---++ Assignment
   1. Complete the program described above.  You will have access to a solution if you wish to use it instead of your own from the previous lab.
   1. Add a method called <b>isDeterministic</b> to the FSM class that returns a boolean to indicate if the machine is deterministic or nondeterministic
   1. Add a method call <b>nTest</b> that returns ACCEPT or REJECT if a nondeterministic machine accepts or rejects a string.  It should only reject if all possible paths fail
      a. You may assume you will not get caught in an infinite recursive situation.
   1. Change in input
      a. File the lines of transitions a "\" indicates and null transition (i.e. does not use up any input)
   1. Be sure to modify the comments as appropriate and maintain good programming techniques  
---++ Submission instructions
   1. Complete the SDR.  Be aware that the form has changed!  Include at least one more set of tests for your own machine along with any other tests you think are appropriate.    Your testing report should probably not be more than a page and could be less.
   1. Combine your SDR and all of your .java and testing files into one zip folder
   1. Submit the zip folder on Canvas by the due data specific there.
---++ Restriction:
It is very likely that there are programs that can be downloaded that can simulate a FSM and/or a NFSM.  You are not allowed to even look at these.  The code provided is what you should use.  This assignment is to bring back your programming skills.
---++ Challenges
   1. Determine if the machine could cause infinite recursion.  There is not help for this (and you are not allowed to use the Internet).  Try to determine what would cause infinite recursion or an infinite loop and test for that.  This is a serious challenge.  Don't even think about it until you finish rest of the assignment with good clean code and you have caught up with all other homework and studying for all your other classes!!!!
Topic revision: r3 - 2022-08-22 - cathybareiss