Practical - 05

Discussion:

As per the AIM, set of valid strings that can be generated by given language is represented in set A:
A = {(),(()), ()(), (()), ((()(()))) ...}
means all the parenthesis that are open must closed or combination of all legal parenthesis formation. Here, opening par is '(' and closing parenthesis is ')'. 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}
Σ: set of input symbols: {(, )}
Г: Set of stack symbols: {(, 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. It is must that the first symbol should be '('.
2. If the input symbol of string is '(' and stack top is Z then push symbol '(' into stack and read the next character in input string.
3. If next character is again '(', then push '(' again in stack and repeat the same process for all '(' in input string.
4. If character is ')' and stack top is '(', then pop '(' from stack.
5. If all the characters of input string are parsed and stack top is Z, it means string is valid, pop Z from stack and change the state from q0 to q1.

Transition Diagram

Figure 2: PDA that accept the well-formed parenthesis.

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 parenthesis string (string character should be '(' and ')')\n";
	gets(Input);
	stack[++Top] = 'Z';//Taking 'Z'as an initial stack symbol.
	int i=-1;
	q0:
		i++;
		if(Input[i]=='(' && stack[Top]== 'Z')
		{
			stack[++Top]= '(';
			goto q0;
		}
		else if(Input[i]=='(' && stack[Top]== '(')
		{
			stack[++Top]= '(';
			goto q0;
		}
		else if(Input[i]==')' && stack[Top]== '(')
		{
			Top--;
			goto q0;
		}
		else if(Input[i]=='\0' && stack[Top]== 'Z')
		{
			Top--;
			goto q1;
		}
		else
		{
			goto Invalid;
		}
	q1:
		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