Practical - 07

Discussion:

As per the AIM, Input can be any binary string and we have to design a turing machine that can calculate its two's complement.
For example (as shown in Figure 1) if the input binary string is 1011010000 then its two's complement will be 0100110000. For constructing a turing machine if we look in the logic then if we read the input string from right to left then the output string will remain exactly the same until the first 1 is found and as the first 1 encounter, complement of rest string appear in the output.

Figure 1: Input outpur relationship of 2's complement of binary string while reading right to left.

Let M be the Turing Machine for above AIM, hence it can be define as M(Q, Σ, Г, δ, q0, B, F) where
Q: set of states: {q0, q1, q2}
Σ: set of input symbols: {0, 1}
Г: Set of Tape symbols: {0, 1, B}
q0: initial state (q0)
B: Blank Symbol (B)
F: set of Final states: { } [Note: Here, set of final states is null as here we have to design turing machine as enumerator.]
δ: Transition Function:

Rules for implementing turing machine for a given language

1. Move the input head at right direction, till it reaches to B. If B encounter then change state from q0 to q1.
2. Now, start reading input symbol right to left one by one.
3. If the input symbol is 0, move the input head left and do the same for all 0 till 1 encounter.
4. If the input symbol is 1, move the input head left and change its state from q1 to q2.
5. Now, if the input symbol is 0, make it 1 and if input symbol is 1 make it 0 till reach to the starting point.

Code in C++

			
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
void main()
{
	char Input[100];
	clrscr();
	cout<<"Enter input binary string\n";
	gets(Input);
	int i=0;
	q0:
		if(Input[i]=='0'|| Input[i]=='1')
		{
			i++;
			goto q0;
		}
		else if(Input[i]=='\0')
		{
			i--;
			goto q1;
		}
		else
		{
			goto Invalid;
		}
	q1:
		if(Input[i]=='0')
		{
			i--;
			goto q1;
		}
		else if(Input[i]=='1')
		{
			i--;
			goto q2;
		}
		else
		{
			goto Invalid;
		}
	q2:
		if(Input[i]=='0')
		{
			Input[i]='1';
			i--;
			goto q2;
		}
		else if(Input[i]=='1')
		{
			Input[i]='0';
			i--;
			goto q2;
		}
		else if(i== -1)
		{
			goto q3;
		}
		else
		{
			goto Invalid;
		}
	q3:
		cout<<"\nOutput: Two's complement is";
		puts(Input);
		goto exit;
	Invalid:
		cout<<"\n You have entered some invalid string.";
		goto exit;
	exit:
		getch();
}
			

Prepared By

Piyush Garg,
Asst. Professor,
Department of CSE, CIST
E-mail: piyushgarg1985@yahoo.com