COSC5315 Program-3 QuadTM-STP Conversion Due: 11/5/2012. Task: Write a well-structured program that does: 1. Read all input quadruples of a TM and echo print them. 2. Convert the input Quadruple TM into an equivalent Semi-Thue Process (STP) and print out all production rules of the resulting STP. Conventions: 1. You must use the same notations used in our web pages for the symbols of the resulting STP. 2. You must use 'B' for the Blank-Space. Input TMs: Use two input TM's: One is given but the other one you need to design. A. TM for L = {u w | u in {1,2}+ and w is the Reverse of u} 1. Move to the rightmost input symbol unchanged. Q1 B R Q1 //Reject the empty input string Q1 1 B Q2 //Leftmost=1 Q1 2 B Q3 //Leftmost=2 Q2 B R Q4 Q4 B B Q4 //Reject odd length. Q4 1 R Q5 //Get to rightmost symbol (1 or 2) Q4 2 R Q5 //Same Q5 1 R Q5 //Same Q5 2 R Q5 //Same Q5 B L Q6 //End of input string rightend, so go left. Q6 1 B Q7 //Matching rightmost symbol (1) Q6 2 2 Q6 //Unmatching, so reject Q6 B B Q6 //Impossible but just in case (Reject) Q3 B R Q8 //Start to move right looking for matching 2. Q8 B B Q8 //Odd length (Reject) Q8 1 R Q9 Q8 2 R Q9 Q9 1 R Q9 Q9 2 R Q9 Q9 B L Qa //End of rightend, so move left. Qa 2 B Q7 //Matching rightmost symbol (2) Qa 1 1 Qa //Unmatching, so reject. Qa B B Qa //Impossible, but just in case. 2. Move to leftmost input symbol unchanged. Q7 B L Qb //Qb is the only accepting state //when no input symbol remains. Qb 1 L Qc Qb 2 L Qc Qc 1 L Qc Qc 2 L Qc Qc B R Q1 //Just passed the leftmost symbol, so //move right to get to it. //At Q1, the current symbol must be 1 or 2. B. You design another input TM for: L2 = {uu|u in (1,2)+} :+ here is a superscript Requirements: You are required to turn in 1. a hardcopy listing of your source program and all required program outputs and 2. A Hand-written derivation sequence by the resulting STP of the first input TM above for the following accepted string: 2112