We discussed in class how a pushdown automaton with two stac

We discussed in class how a pushdown automaton with two stacks would be able to accept strings in the non-context-free language AnBnCn (“n a’s followed by n b’s followed by n c’s”).

Algorithm Sketch: read a’s and push them onto stack1, while reading b’s pop stack1 for each b and push one b onto stack2; while reading c’s, pop stack2; the string is accepted when the string is completely read and stack1 and stack2 are empty, otherwise, the string is not in AnBnCn. (Work out the finer points by thinking through the various scenarios of mismatched numbers of a’s, b’s , and c’s, and unacceptable permutations of these symbols. This will help prevent undesirable run-time behaviors/crashes of your program , e.g., attempts to pop an empty stack.)

In a programming language of your choice (likely C++, possibly Python, or Java, or … ), write a simple program that reads a string of characters in {a,b,c} , once from left to right, and uses two stacks in order to determine whether or not the input string is a member in AnBnCn.

Note: You are not asked to write a program that “simulates” the process of a formal PDA as we have studied. I.e., your program will not read next state/stack configurations off a transition table. Instead, freely write a program to accomplish the task in the manner by which a student would so fresh out of basic CSE. In order to qualify for extra credit, your program must fulfill the following requirements:

• It must correctly identify membership or non-membership for all 64+4 sample inputs listed below.

• It must do so without any counting of frequencies for symbols ‘a’, ‘b’, and ‘c’.

• It must use two stacks (either use an explicit stack data structure or use another suitable data structure in stack fashion.)

• It must have been designed and implemented by yourself, individually, not as a team.

• Your program must feature a Boolean function which determines for a given string whether or not it is in AnBnCn. (No “big main()” without functions!).

Solution

// program for pushdown automata for AnBnCn.
// aabbcc or aaabbbccc are acceptable and ababcc , a, b, c, abcabcabc are not acceptable.
// using stacks explicitly implemented below.

import java.util.Scanner;
public class PushDA{
   static int maxChar = 100;                   // maximum chars 100 in string if you want change the value here
   static Stack stack1 = new Stack(maxChar);   // stacks for counting          
   static Stack stack2 = new Stack(maxChar);
   public static void main(String args[]){
       Scanner sc = new Scanner(System.in);
       String input = sc.nextLine();           // prompting for input
       boolean result = anBnCn(input);                               // calling function
       if(result == true){                               // result
           System.out.println(result+\" \\\"\"+ input + \"\\\" belongs to AnBnCn family\");
       }      
       else{
           System.out.println(result+\" \\\"\"+ input + \"\\\" does not belongs to AnBnCn family\");
       }
   }
   public static boolean anBnCn(String input){
       int length = input.length();
       int i=0;
       while(i<length && input.charAt(i)!=\'b\'){       // loop until b appears.
           if(input.charAt(i)!=\'a\'){               // this is for direct \'c\' before \'a\' and \'b\'
               return false;
           }
           else{
               stack1.push(\'a\');                   // if a push into stack1
               i++;
           }
       }
       while(i<length && input.charAt(i)!=\'c\'){
           if(input.charAt(i)!=\'b\'){               // this is for situations like if \'a\' comes after \'b\'
               return false;
           }
           else{
               if(stack1.isEmpty()){               // \'b\'s are more than \'a\'s
                   return false;
               }
               stack1.pop();                   // poping \'a\'
               stack2.push(\'b\');               // pushing \'b\'
               i++;
           }
       }
       if(!stack1.isEmpty()){           // if \'b\'s are less than \'a\'s
           return false;
       }
       while(i<length){
           if(input.charAt(i)!=\'c\'){       //if it is not \'c\' after \'a\' and \'b\'
               return false;
           }
           else{
               if(stack2.isEmpty()){       // if more \'c\'s
                   return false;
               }
               stack2.pop();           // poping \'b\'s
               i++;
           }
       }
       if(!stack2.isEmpty()){       // if less no of \'c\'s
           return false;
       }
       return true;                // every thing is fine
   }      
}
// definition of stack
class Stack {
   private int max;
   private char[] stackArray;
   private int top;
   public Stack(int s) {
      max = s;
      stackArray = new char[max];
      top = -1;
   }
   public void push(char j) {
      stackArray[++top] = j;
   }
   public char pop() {
      return stackArray[top--];
   }
   public char peek() {
      return stackArray[top];
   }
   public boolean isEmpty() {
      return (top == -1);
   }
   public boolean isFull() {
      return (top == max - 1);
   }
}

// end of program