CS154 FALL 2021 TERM PROJECT
INTRODUCTION
In this project, you will design and implement a standard Turing Machine (TM) that simulates DFA. The result TM can
decide whether the DFA accept or rejects a string.
INPUT AND OUTPUT
The input includes an encoded DFA and an encoded string that needs to be input into the DFA. The TM will be running
under transducer mode and output is based on whether the DFA accepts the string or not.
INPUT ENCODING
The input for your TM has 3 parts:
• The input string w for the DFA
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 DFA can be λ (this part is empty).
• Transition function δ of the DFA
Each state is encoded into a unary number, so that q0 is 1, q1 is 11, q2 is 111, etc.
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 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.
Note that the transitions are NOT ordered.
• All accepting states of the DFA
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 DFA.
Note that the states are NOT order, and 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 DFA accept the string w, the output of your TM should be A;
• If the DFA reject the string w, the output of your TM should be R.
EXAMPLE
Input of your TM (with explanation)
□ □ 1 0 1 1 D 1 1 0 1 1 0 1 1 D 1 0 1 0 1 D 1 1 0 1 0 1 1 D 1 0 1 1 0 1 1 F 1 □ □
Input string
w to the
DFA (ab)
current state q1
current
symb. b
next
state q1
One transition
(sub-rule of δ)
One transition
(sub-rule of δ)
One transition
(sub-rule of δ)
Accept.
States
{q0}
Transition function δ of the DFA
The whole DFA
Input string to the DFA is ab, equivalent DFA as below. Since the DFA rejects ab, Output of the TM 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.
• Due date is Friday, Dec. 3, 23:59 PDT.
• You will know your score, as well as all the test cases I used, no later than Saturday, Dec. 4, 23:59 PDT, and you can
resubmit your work with -5% late penalty before Monday, Dec. 6 23:59 PDT.
• You can choose to use the score for this project to substitute your final score, so you don’t need to take the final.
Answer the last question on Term Project or email me about your decision by Monday, Dec. 6 23:59 PDT.
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.
Introduction
Input and Output
Input Encoding
Output
Example
Technical Notes
Submission
Rubrics
Other Suggestions