search

Aunsiels / pyformlang

A python library to manipulate formal languages and various automata
https://pypi.org/project/pyformlang/
MIT License
43 stars 10 forks source link

Question: PDA final state or empty stack? #7

Closed atticus-sullivan closed 3 years ago

atticus-sullivan commented 3 years ago

Hi, I read your doc on readthedocs and browsed through the code, but I'm still not sure when which type of PDA is used.

When adding the transitions step by step to the PDA, should this be a PDA accepting on final state or on empty stack? Is this determined by checking whether final_state contains some states?

I noticed that when calling to_final_state() and to_empty_stack() in either calls the (same) automata changed. Is it assumed that the automata is in accept by state mode when calling to_empty_stack() and analog for accept by empty stack? (the thought of the functions assuming a mode of the PDA comes to me by the comments like Turns the current PDA final state to empty stack)

Then when converting to CFG, is it also assumed that the automata was in accept by empty stack (that's how I'd interpret the comment Turns this PDA on empty stack accepting into a CFG)?

Please elaborate on what is set how and what is assumed.

Aunsiels commented 3 years ago

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?

atticus-sullivan commented 3 years ago

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 ;)