Construct a program any language that reads a string of char

Construct a program (any language) that reads a string of characters from either \'a\' or \'b\' or \'c\' to solve whether the string of input is a member of...

We discussed 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 Ha,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 It must correct 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.) 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

import random

# generate inputs
def generate_inputs():
   asubs = [\"\",\"aaa\",\"aaaaaa\",\"aaaaaaaaa\"]
   bsubs = [\"\",\"bbb\",\"bbbbbb\",\"bbbbbbbbb\"]
   csubs = [\"\",\"ccc\",\"cccccc\",\"ccccccccc\"]

   all_abc = []
   for a in asubs:
       for b in bsubs:
           for c in csubs:
               all_abc.append(a+b+c)

   random.seed()
   for i in range(4):
       rstr = list(random.choice(all_abc))
       random.shuffle(rstr)
       rstr = \'\'.join(rstr)
       all_abc.append(rstr)
   return all_abc

# check memebrship of a string
# False if -
#   1. trying to pop from empty stack
#   2. non empty stacks at the end of reading complete string
# True if -
#   both stacks are empty at the end of reading complete string
def check_membership(member):
   stack1 = []
   stack2 = []
   for c in member:
       if(c==\'a\'):
           stack1.append(c)
       elif(c==\'b\'):
           stack2.append(c)
           if(stack1==[]):
               return False
           stack1.pop()
       elif(c==\'c\'):
           if(stack2=c=[]):
               return False
           stack2.pop()
       else:
           return False
   if(stack1==[] and stack2==[]):
       return True
   else:
       return False

def main():
   all_abc = generate_inputs()
   for abc in all_abc:
       print abc+\" : \"+str(check_membership(abc))

if __name__ == \'__main__\':
   main()

__________________________________________________________________________

Output

: True

ccc : False

cccccc : False

ccccccccc : False

bbb : False

bbbccc : False

bbbcccccc : False

bbbccccccccc : False

bbbbbb : False

bbbbbbccc : False

bbbbbbcccccc : False

bbbbbbccccccccc : False

bbbbbbbbb : False

bbbbbbbbbccc : False

bbbbbbbbbcccccc : False

bbbbbbbbbccccccccc : False

aaa : False

aaaccc : False

aaacccccc : False

aaaccccccccc : False

aaabbb : False

aaabbbccc : True

aaabbbcccccc : False

aaabbbccccccccc : False

aaabbbbbb : False

aaabbbbbbccc : False

aaabbbbbbcccccc : False

aaabbbbbbccccccccc : False

aaabbbbbbbbb : False

aaabbbbbbbbbccc : False

aaabbbbbbbbbcccccc : False

aaabbbbbbbbbccccccccc : False

aaaaaa : False

aaaaaaccc : False

aaaaaacccccc : False

aaaaaaccccccccc : False

aaaaaabbb : False

aaaaaabbbccc : False

aaaaaabbbcccccc : False

aaaaaabbbccccccccc : False

aaaaaabbbbbb : False

aaaaaabbbbbbccc : False

aaaaaabbbbbbcccccc : True

aaaaaabbbbbbccccccccc : False

aaaaaabbbbbbbbb : False

aaaaaabbbbbbbbbccc : False

aaaaaabbbbbbbbbcccccc : False

aaaaaabbbbbbbbbccccccccc : False

aaaaaaaaa : False

aaaaaaaaaccc : False

aaaaaaaaacccccc : False

aaaaaaaaaccccccccc : False

aaaaaaaaabbb : False

aaaaaaaaabbbccc : False

aaaaaaaaabbbcccccc : False

aaaaaaaaabbbccccccccc : False

aaaaaaaaabbbbbb : False

aaaaaaaaabbbbbbccc : False

aaaaaaaaabbbbbbcccccc : False

aaaaaaaaabbbbbbccccccccc : False

aaaaaaaaabbbbbbbbb : False

aaaaaaaaabbbbbbbbbccc : False

aaaaaaaaabbbbbbbbbcccccc : False

aaaaaaaaabbbbbbbbbccccccccc : True

aaaaaa : False

baacaaccaabcaacbcbbbcacc : False

cccccbabacaccbbbbc : False

ccccbaccbbbabbacbbccb : False