Lab 13

LAB 15:
PDA accepting equal numbers of 0’s and 1’s with empty stack PDA description:

It starts at q0 and pushes $ into the empty stack. At the same state q0,
PDA pushes input symbol if stack top symbol is $ or stack top is same as
input symbol. Otherwise if input is 0 and stack top is 1 or input is 1
and stack top is 0, stack top is popped off. If input is finished and
stack top is $, PDA accepts the input strings.

Code for PDA Accepting by empty Stack
#include<stdio.h>
#include<string.h>
#define MAX 100
Enum states {q0};
void push(char ch);
void pop();
char get_stack_top();
enum states delta(enum states, char, char);
struct stack
{
           Char symbols[MAX];
           int top;
};
struct stack s;
int main()
{
char input[20];
enum states curr_state=q0;
s.top=-1;
int i=0;
char ch=’e’;
char st_top=’e’;
curr_state=delta(curr_state,ch,st_top);
printf(“\n Enter a binary string\t”);
gets(input);
ch=input[i];
st_top= get_stack_top();
int c=0;
while(c<=strlen(input))
{
curr_state=delta(curr_state,ch,st_top);
ch=input[++i];
st_top=get_stack_top();
c++;
}
if(s.symbols[s.top]==’$’)
printf(“\nThe string %s is accepted.”,input);
else
printf(“\nThe string %s is not accepted.”,input);
return 0;
}
enum states delta(enum states s, char ch, chat st_top)
{
enum states curr_state;
switch(s)
{
case q0;
if(ch==’e’ && st_top==’e’)
{
curr_state = q0;
push(‘$’);
}
else if(ch==’0’ && (st_top==’$’ || st_stop==’0’))
{
curr_state = q0;
push(ch);
}
else if(ch==’1’ && (st_top==’$’ ||st_top==’1’))
{
curr_state = q0;
push();
}
else if(ch==’1’ && st_top==’0’ ||ch==’0’ &&st_top==’1’)
{
curr_state = q0;
pop();
}
else if(ch==’\0’ &&st_top==’$’)
{
curr_state = q0;
//pop();
}
break;
}
return surr_state;
}
char get_stack_top()
{
return(s.symbols[s.top]);
}
void push(char ch)
{
if(s.top<MAX-1)
{
s.symbols[++s.top] =ch;
}
else
{
printf(“\nStack Full.”);
}
}
void pop()
{
if(s.top>-1)
{
s.symbols[s.top]=’ ‘;
s.top--;
}
else
printf(“\nStack Empty.”);
}