Question: PDA final state or empty stack? about pyformlang HOT 2 CLOSED

Hi,

The pushdown automata accepting by empty stack and the pushdown automata accepting by final state have the same representation based on 7-tuples (see Hopcroft or Wikipedia for the complete definition). Therefore, Pyformlang represents them with the same class and it is the user who decides whether they want the language represented by final state acceptance or empty stack acceptance. It is true that it can be confusing when performing transformations between CFG and these two acceptance modes: Nothing indicates that you must use your PDA by accepting by final states or by empty stack to obtain a language equivalent to what you were manipulating before.

For the two functions to_final_state() and to_empty_stack(), the input and output are what we expect. to_final_state() supposes that the user provides a PDA P that generates by empty stack a language L and it returns a PDA P' that generates by final states the same language L (but it generates another language by empty stack).

For the functions to_pda() (applied to a CFG) and to_cfg(), it is important to remember that the transformation involves two representations of the same language. The first one is a context-free grammar and the second is a push-down automaton when accepting by empty stack. However, nothing forces the user to use the PDA to accept by empty stack only.

I tried to clarify a bit the documentation. Also, for the intersection function, it was not clear that it involves a PDA when accepting by final state.

What are your thoughts about it? Do you think we should add the possibility to force the acceptance mode and add warning messages?

from pyformlang.

Ah yes right, this makes it more clear for me. I'm not quite sure about enforcing the acceptance mode, but I think this would make it more clear and possible for the user to check in which mode the PDA is.

Maybe some sort of a boolean indicating the acceptance mode, which is given to the PDA on creation and of which the PDA keeps track on its own later on (conversions...). For backwards compatibility reasons, this attribute could be set to some kind of ignore checks value (but this eliminates the thought of using a boolean for this).

But this is just my opinion, and to be honest, I'm not that experienced in programming in bigger structures ;)

from pyformlang.