Practical - 06

Discussion:

As per the AIM, set of valid strings that can be generated by given language is represented in set A:
A = {0C0, 1C1, 011000110C011000110, 101011C110101, ....}
means string must have some binary string followed by special character 'C' followed reverse of binary string that appears before 'C'. Block diagram of push down automata is shown in Figure 1.

Figure 1: Block Diagram of Push Down Automata.

Input string can be valid or invalid, valid if the input string follow set A (define above). PDA has to determine whether the input string is according to the language or not.

Let M be the PDA machine for above AIM, hence it can be define as M(Q, Σ, Г, δ, q0, Z0, F) where
Q: set of states: {q0, q1, q2}
Σ: set of input symbols: {0, 1, C}
Г: Set of stack symbols: {A, B, Z}
q0: initial state (q0)
Z0: initial stack symbol (Z)
F: set of Final states: { } [Note: Here, set of final states is null as decision of validity of string is based on stack whether it is empty or not. If empty means valid else invalid.]
δ: Transition Function: (Transition state diagram is shown in Figure 2.)

Rules for implementing PDA for a given language

1. If the input symbol of string is '0' and stack top is Z then push symbol 'A' into stack and read the next character in input string.
2. If the input symbol of string is '1' and stack top is Z then push symbol 'B' into stack and read the next character in input string.
3. If the input symbol of string is '0' and stack top is A or B then push symbol 'A' into stack and read the next character in input string.
4. If the input symbol of string is '1' and stack top is A or B then push symbol 'B' into stack and read the next character in input string.
5. If the input symbol of string is 'C' and stack top is A or B then change state from q0 to q1 and read the next character in input string.
6. If the input symbol of string is '0', machine state is q1 and stack top is A then pop stack top and read the next character in input string.
7. If the input symbol of string is '1', machine state is q1 and stack top is B then pop stack top and read the next character in input string.
8. If all the characters of input string are parsed, stack top is Z and machine state is q1, it means string is valid, pop Z from stack and change the state from q1 to q2.

Transition Diagram

Figure 2: PDA that accept language WCW^R where w is any binary string and W^R is reverse of that string and C is a special symbol.

Code in C++

			
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
void main()
{
	char Input[100];
	char stack[100];
	int Top = -1;
	clrscr();
	cout<<"Enter string to be validate\n";
	gets(Input);
	stack[++Top] = 'Z';//Taking 'Z'as an initial stack symbol.
	int i=-1;
	q0:
		i++;
		if(Input[i]=='0' && stack[Top]== 'Z')
		{
			stack[++Top]= 'A';
			goto q0;
		}
		else if(Input[i]=='1' && stack[Top]== 'Z')
		{
			stack[++Top]= 'B';
			goto q0;
		}
		else if(Input[i]=='0' && (stack[Top]== 'A'|| stack[Top]== 'B'))
		{
			stack[++Top]= 'A';
			goto q0;
		}
		else if(Input[i]=='1' && (stack[Top]== 'A'|| stack[Top]== 'B'))
		{
			stack[++Top]= 'B';
			goto q0;
		}
		else if(Input[i]=='C' && (stack[Top]== 'A'||stack[Top]== 'B'))
		{
			goto q1;
		}
		else
		{
			goto Invalid;
		}
	q1:
		i++;
		if(Input[i]=='0' && stack[Top]== 'A')
		{
			Top--;
			goto q1;
		}
		else if(Input[i]=='1' && stack[Top]== 'B')
		{
			Top--;
			goto q1;
		}
		else if(Input[i]=='\0' && stack[Top]== 'Z')
		{
			goto Valid;
		}
		else
		{
			goto Invalid;
		}
	Valid:
		cout<<"\n Output: Valid String";
		goto exit;
	Invalid:
		cout<<"\n Output: Invalid String";
		goto exit;
	exit:
		getch();
}
			

Prepared By

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