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