Deterministic Pushdown Automata for L = a^nb^n | n >=0) Python Program

Question

The python code I wrote and ran for the program. It does what I want it to do for the project, but I really don't like how I structured the code and I feel like I could have labelled and shortened so much of my code. Any advice? I want to make it shorter and maybe clean it up more. OR if you have another idea of how you would implement the code in python, I would greatly appreciate seeing how you would do it. I will link the prompt to my project below.

Answer 1

Here is how you can implement the class DPDA for the CFL a^nb^n, using the following states, stack symbols and transition function from here:

class DPDA:
    
    def __init__(self, trf, input, state):
        
        self.head = 0
        self.trf = {}
        self.state = str(state)
        self.input = input
        self.trf = trf
        self.stack = ['Z']
        
    def step(self):
        
        a = self.input[self.head]
        s = self.stack.pop()
        state, ss = self.trf.get((self.state, a, s))
        if ss != 'ε':
            for s in ss[::-1]:
                self.stack.append(s)
        self.state = state
        print('{:20s} [{:10s}] {:5s}'.format(self.input[self.head:], 
                       ''.join(self.stack), self.state))        
        self.head += 1
    
    def run(self):
        
        print('{:20s} [{:10s}] {:5s}'.format(self.input[self.head:], 
                              ''.join(self.stack), self.state))
        
        while self.head  < len(self.input):
            self.step()

        s = self.stack.pop()        
        if self.trf.get((self.state, 'ε', s)):
            state, ss = self.trf.get((self.state, 'ε', s))
            self.state = state        
            print('{:20s} [{:10s}] {:5s}'.format('ε', 
                 ''.join(self.stack), self.state))
        
# run DPDA to accept the input string a^9b^9
DPDA({('q', 'a', 'Z'): ('q', 'XZ'),
     ('q', 'a', 'X'): ('q', 'XX'),
     ('q', 'b', 'X'): ('p', 'ε'),
     ('p', 'b', 'X'): ('p', 'ε'),
     ('p', 'ε', 'Z'): ('acc', 'Z'),
    }, 
    'aaaaaaaaabbbbbbbbb', 'q').run()

#input                #stack       #state
#aaaaaaaaabbbbbbbbb   [Z         ] q    
#aaaaaaaaabbbbbbbbb   [ZX        ] q    
#aaaaaaaabbbbbbbbb    [ZXX       ] q    
#aaaaaaabbbbbbbbb     [ZXXX      ] q    
#aaaaaabbbbbbbbb      [ZXXXX     ] q    
#aaaaabbbbbbbbb       [ZXXXXX    ] q    
#aaaabbbbbbbbb        [ZXXXXXX   ] q    
#aaabbbbbbbbb         [ZXXXXXXX  ] q    
#aabbbbbbbbb          [ZXXXXXXXX ] q    
#abbbbbbbbb           [ZXXXXXXXXX] q    
#bbbbbbbbb            [ZXXXXXXXX ] p    
#bbbbbbbb             [ZXXXXXXX  ] p    
#bbbbbbb              [ZXXXXXX   ] p    
#bbbbbb               [ZXXXXX    ] p    
#bbbbb                [ZXXXX     ] p    
#bbbb                 [ZXXX      ] p    
#bbb                  [ZXX       ] p    
#bb                   [ZX        ] p    
#b                    [Z         ] p    
#ε                    [Z         ] acc  

The next animation shows how the string is accepted by the above DPDA: