INTRODUCTION

In this project, you will design and implement a standard Turing Machine (TM) that simulates MDFAs, where MDFA means Modified DFA that can have 0 transition during a timeframe (everything else is the same as a regular DFA). The result TM can decide whether an MDFA accepts or rejects a string.

INPUT AND OUTPUT

The input includes an encoded MDFA and an encoded string that needs to be input into the MDFA. The TM will be running under transducer mode and output is based on whether the MDFA accepts the string or not.

INPUT ENCODING

The input for your TM has 3 parts:

• The input string w for the MDFA
  
  Each symbol is encoded into a unary number and separated by a 0 (zero).
  In this project, the input symbol will be English lowercase letters. 1 is a, 11 is b, 111 is c, etc.
  For example, 10111011 means acb. Note that the input string for the MDFA can be λ (this part is empty).
  

• Transition function δ of the MDFA

Each state is encoded into a unary number, so that q0 is 1, q1 is 11, q2 is 111, etc; q0 is always the initial state. 

Each transition starts with D. And each transition has 3 parts, separated by a 0 (zero):

o Current state: 1, 11, 111, etc. Only one current state per transition;

                        o Read condition: same as the encoding for the input: 1 is a, 11 is b, etc. Only 

                           one current symbol per transition

                        o Next state: 1, 11, 111, etc. Only one next state per transition.

For example, D11010111 means if the current state is q1, and the current symbol is a, transit to q2.

The transitions are ordered by the current state, then the read condition. For example, D101101 will come before D110101; D10101 will come before D101101, etc.

• All accepting states of the MDFA

This part starts with an F. States are separated by a 0 (zero)

For example, F1011 means q0 and q1 are the accepting states of the MDFA.

Final states are also ordered from the smallest. For example, F10111; will never be something like F11010111 Note that there may be no final states. But the F will still be there.

OUTPUT

Your TM will be running under transducer mode. Your TM should accept the input, and output a capital letter (A or R):

• If the MDFA accept the string w, the output of your TM should be A;
  

• If the MDFA reject the string w, the output of your TM should be R.
  
  EXAMPLE
  
  Suppose the input string to the MDFA is ab, and here is the MDFA.
  

Since the MDFA rejects ab, Output of the TM should be R. The input of the TM (with explanation) is on the next page.

Input of your TM (with explanation). Output should be R.

TECHNICAL NOTES

• We assume that the input string of TM is 100% correct. Therefore, your TM is NOT supposed to have any error detection and/or error reporting. If the input string is incorrect, the machine just stops, and it can show anything!
  

• You can use Turing Machine With Building Blocks feature in JFLAP. Follow the same procedure as showed in class:
  o First, design each block (TM), then insert them as blocks into the .jff for the main design.

o If you want to edit any block, first edit the original file for that block and save it, then in the .jff for the main design, delete and insert the block again.

o Always have a backup of your current work before modifying it.

      • You can use the Stay option, ! and ~ symbol if needed. For more information, please refer  to the lecture notes as well as JFLAP's documentations and tutorials.

SUBMISSION

• Can have a group up to 3. But each group member should finish and submit the Term Project “quiz” on Canvas. It is an untimed Quiz, and you can submit as many times as you want, no access code!
  

• You should submit only one .jff file: main design with all the blocks inserted.
  

 RUBRICS

• Your design will be tested and graded with 20 test cases, +3.5 for every success pass (70 points total).
  

• You'll get zero If your design can’t run (no initial state, incompatible, etc.); -5% late penalty for resubmission.
  

OTHER SUGGESTIONS

• Always read the requirements at least 10 times! An inaccurate developer is unacceptable!
  

• Always set the due date for yourself at least 2-3 days before the official due date.
  

• After submitting your work, always download it and test it to make sure that the process of submission was fine.
  

• Always make sure that you have the latest version of this document. Sometimes, based on your questions and feedbacks, I need to add some clarifications. If there is a new version, it will be announced via Canvas.
  

• You can open a discussion to share your test cases. I might use them for grading If your test cases are smart and tricky! Note this is the ONLY thing you can share about this project publicly!
  

• If there is any ambiguity, question, or concern about the project requirements, please open a discussion in Canvas.