Practical - 04

Discussion:

As per the AIM, set of valid strings that can be generated by given language is represented in set A:
A = {01, 0011, 000111, ...}
means all string having n number of 0's followed by n numbers of 1's where n can be any number greater than equal tp and count of 0's must be equal to count of 1's. 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 it follows the language 0ⁿ1ⁿ where n >= 1 else invalid. 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}
Г: Set of stack symbols: {A, Z0}
q0: initial state (q0)
Z0: initial stack symbol (Z0)
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.]
δ: Transition Function: (Transition state diagram is shown in Figure 2.)

Rules for implementing PDA for a given language

1. It is must that the first symbol should be 0. If the first symbol of input string is zero then push symbol 'A' into stack and read the next character in input string.
2. If next character is again 0, then push A again in stack and repeat the same process for all consecutive 0's in input string.
3. If next character is 1, then pop A and change its state from q0 to q1.
4. If again the next character is 1 and top symbol of stack is 'A', then pop A and repeat the same process for all consecutive 1's in input string.
5. If all the characters of input string are parsed and stack top is Z0, it means string is valid, pop Z0 from stack and change the state from q1 to q2.

Transition Diagram

Figure 2: PDA - accepting string for a language 0ⁿ1ⁿ where n >= 1.

Code in C++

			
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
void main()
{
	char Input[100];
	char stack[100]; //Implementing stack through array.
	int Top = -1;
	clrscr();
	cout<<"Enter binary string to validate (input string should be of 0 and 1)\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]=='0' && stack[Top]== 'A')
		{
			stack[++Top]= 'A';
			goto q0;
		}
		else if(Input[i]=='1' && stack[Top]== 'A')
		{
			Top--;
			goto q1;
		}
		else
		{
			goto Invalid;
		}
	q1:
		i++;
		if(Input[i]=='1' && stack[Top]== 'A')
		{
			Top--;
			goto q1;
		}
		else if(Input[i]=='\0' && stack[Top]== 'Z')
		{
			Top--;
			goto q2;
		}
		else
		{
			goto Invalid;
		}
	q2:
		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