Deterministic Pushdown Automata for L = a^nb^n | n >=0) Python Program
source link: https://stackoverflow.com/questions/65228027/deterministic-pushdown-automata-for-l-anbn-n-0-python-program/70160889
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Deterministic Pushdown Automata for L = a^nb^n
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.
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:
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK