push down automata

[goyalyashpal]

i find the bare minimal input/specification format of https://ivanzuzak.info/noam/webapps/fsm_simulator/ to be awesome.

and i have tried varioud other online PDA simulators, bur they mix presentation (coordinates), storage (json), and data (actual machine) in their input format which makes it cumbersome to enter and export.

so, can the push-down-automata be supported as well 😃

[goyalyashpal]

sample pda machine in same ivazuzak's format:

for the Language:

L = { a³ⁿ⁺¹ bᵗ c²ᵗ ⁺² dⁿ | n>=0, m>=1 }

#states
s0
s1
s2
s3
s4
s5
s6
s7
s8
#initial
s0
#accepting
$
#alphabetinputtape
a
b
c
d
#alphabetstack
Z
c
d
$
#transitions
s0:a,Z,Z>s1
s1:a,Z,Z>s2
s2:a,Z,Z>s3
s3:a,Z,dZ>s1
s1:a,d,d>s2
s2:a,d,d>s3
s3:a,d,dd>s1
s1:b,Z,ccZ>s4
s1:b,d,ccd>s4
s4:b,c,ccc>s4
s4:c,c,c>s5
s5:c,c,c>s6
s6:c,c,$>s6
s6:$,Z,$>s8
s6:d,d,$>s7
s7:d,d,$>s7
s7:$,Z,$>s8

notable differences from *FA:

• 3 transition symbols: input, stack, changeonstack
  • b,c,ccc means read b from tape, c from stack, and replace the last single symbol of stack with ccc
  • some textbooks use input, stack | changeonstack i.e. vbar instead of comma, but i guess the comma makes it easy to input
• there can be 2 ways of accepting PDA: empty stack ($) or final state. above eg uses empty stack.
• DPDA reads empty alphabet only on last transition
• Z and $ are sentinel symbols for stack meaning bottom of stack (no additional symbol) and empty stack (no symbol at all) respectively.
• there can be ways to condense the similar transitions, but they will make syntax ugly, and parsing hard. so, explicit is better i guess.

[izuzak]

@goyalyashpal Thanks so much for creating this issue. Yeah, I agree this would be useful -- I always planned on implementing PDAs as well, but never got around to it. I also appreciate that you explained how the format would need to be extended and how the simulation would work.

I can't promise I'll work on such a feature in the near future, so if you'd like to give this a try and implement it yourself -- let me know and feel free to open a pull request!

Thanks again 🙇