no reading of the stack

[thiagogquinto]

if I in the code put to read '' in the stack, the input will replace what there is in te stack or the input will be on the top with no replacing of what it is in the stack?

[caleb531]

@thiagogquinto The way the stack works in this library (replacing the stack, empty string, etc.) is according to how I was taught pushdown automata in my CS theory class. In that class, an empty string (meaning lambda/epsilon) causes the machine to pop the top element from the stack.

There's a great example in the NPDA docs that shows the different ways you can interact with the stack on each transition.

[thiagogquinto]

Ok, but to be sure, the code 'q0': { 'a': { '#': {('q2', 'a')}, }, code means that currently you are int he state q0 and you got an 'a' form the input, and in the top of the stack there is the '#', if I use this code, if inte code replace the '#' for '', in this case, I would consume nothing of the stack, right? Then in the stack after the execution the stack would have '#a"?

[caleb531]

@thiagogquinto Upon reviewing my code, I realized that my comments are backwards. It's clear if you look at the implementation for how elements are actually pushed to the stack in automata/pda/stack.py:

def replace(self, symbols):
    """
    Replace the top of the stack with the given symbols.

    Return a new PDAStack with the new content.
    The first symbol in the given sequence becomes the new stack top.
    """
    stack_contents = list(self.stack)
    stack_contents.pop()
    stack_contents.extend(reversed(symbols))
    return self.__class__(stack_contents)

Note the reversed, which means that the first element of the tuple represents the new top of the stack. And if you have only one element in your tuple, then you are either not changing the stack at all OR replacing the top without adding any new elements.

For example, if the top of the stack is # and you want to add 'A', then your tuple should be ('A', '#') (regardless of what my comments say, this seems to be consistent with how I've defined the transitions).

I will make it a priority to correct this in the documentation. My sincere apologies for the confusion.

[thiagogquinto]

Ok, thank you for the help!

[caleb531]

@thiagogquinto I have just updated the PDA docs. Please let me know if this makes sense to you now:

https://github.com/caleb531/automata/blob/main/docs/pda/class-dpda.md https://github.com/caleb531/automata/blob/main/docs/pda/class-npda.md

[thiagogquinto]

Makes sense, so in every input I have to 'check' what it is in the stack, right? Because I am using your library for a parser, and It is many possible things that might be in the top of the stack rsrsrs. But thank you for the help, this is already very useful. Sorry for bothering.

[caleb531]

@thiagogquinto Don't be sorry at all! You helped me fix a mistake in the documentation, and I am grateful for that.

And correct, if you are pushing to the stack, you do need to know what is currently on the stack when defining the transitions. However, because of how this library defines PDAs in Python code, you should already be able to tell what is currently on the stack by examining the transition you are on.

What do I mean by that? Well, the innermost dictionary keys represent the (respective) current symbols on the stack. For example, in these transitions, you know that '#' is the current top of the stack (before pushing) for both transitions because '#' is the innermost key of each transition.

{
    'q0': {
        '': {
            '#': {('q2', '#')},  # no change to stack
        },
        'a': {
            '#': {('q0', ('A', '#'))}  # push 'A' to stack
        }
    }
}

Hence, if you are constructing these PDAs programmatically in your parsing code, then you should already have the information you need to get the current top of the stack.