Push-Down Automata¶
pyformlang.pda
¶
This module deals with push-down automata.
Available Classes¶
- PDA
A Push-Down Automaton
- State
A push-down automaton state
- Symbol
A push-down automaton symbol
- StackSymbol
A push-down automaton stack symbol
- Epsilon
A push-down automaton epsilon symbol
- class pyformlang.pda.PDA(states: Optional[AbstractSet[State]] = None, input_symbols: Optional[AbstractSet[Symbol]] = None, stack_alphabet: Optional[AbstractSet[StackSymbol]] = None, transition_function: Optional[TransitionFunction] = None, start_state: Optional[State] = None, start_stack_symbol: Optional[StackSymbol] = None, final_states: Optional[AbstractSet[State]] = None)[source]¶
Representation of a pushdown automaton
- Parameters
states (set of
State
, optional) – A finite set of statesinput_symbols (set of
Symbol
, optional) – A finite set of input symbolsstack_alphabet (set of
StackSymbol
, optional) – A finite stack alphabettransition_function (
TransitionFunction
, optional) – Takes as arguments a state, an input symbol and a stack symbol and returns a state and a string of stack symbols push on the stacked to replace Xstart_state (
State
, optional) – A start state, element of statesstart_stack_symbol (
StackSymbol
, optional) – The stack is initialized with this stack symbolfinal_states (set of
State
, optional) – A set of final or accepting states. It is a subset of states.
- add_final_state(state: State)[source]¶
Adds a final state to the automaton
- Parameters
state (
State
) – The state to add
- add_transition(s_from: State, input_symbol: Symbol, stack_from: StackSymbol, s_to: State, stack_to: List[StackSymbol])[source]¶
Add a transition to the PDA
- Parameters
s_from (
State
) – The starting symbolinput_symbol (
Symbol
) – The input symbol for the transitionstack_from (
StackSymbol
) – The stack symbol of the transitions_to (
State
) – The new statestack_to (list of
StackSymbol
) – The string of stack symbol which replace the stack_from
- add_transitions(transitions)[source]¶
Adds several transitions
- Parameters
transitions – Transitions as they would be given to add_transition
- property final_states¶
The final states of the PDA :returns: final_states – The final states of the PDA :rtype: iterable of
State
- classmethod from_networkx(graph)[source]¶
Import a networkx graph into a PDA. The imported graph requires to have the good format, i.e. to come from the function to_networkx
- Parameters
graph – The graph representation of the PDA
- Returns
A PDA automaton read from the graph
- Return type
pda
- get_number_transitions() int [source]¶
Gets the number of transitions in the PDA
- Returns
n_transitions – The number of transitions
- Return type
- property input_symbols¶
The input symbols of the PDA
- Returns
input_symbols – The input symbols of the PDA
- Return type
iterable of
Symbol
- intersection(other: Any) PDA [source]¶
Gets the intersection of the language L generated by the current PDA when accepting by final state with something else
Currently, it only works for regular languages (represented as regular expressions or finite automata) as the intersection between two PDAs is not context-free (it cannot be represented with a PDA).
- Equivalent to:
>> pda and regex
- Parameters
other (any) – The other part of the intersection
- Returns
new_pda – The pda resulting of the intersection
- Return type
- Raises
NotImplementedError – When intersecting with something else than a regex or a finite automaton
- set_start_stack_symbol(start_stack_symbol: StackSymbol)[source]¶
Sets the start stack symbol to the automaton
- Parameters
start_stack_symbol (
StackSymbol
) – The start stack symbol
- set_start_state(start_state: State)[source]¶
Sets the start state to the automaton
- Parameters
start_state (
State
) – The start state
- property stack_symbols¶
The stack symbols of the PDA
- Returns
stack_symbols – The stack symbols of the PDA
- Return type
iterable of
StackSymbol
- property start_state¶
Get start state
- property states¶
Get the states fo the PDA :returns: states – The states of the PDA :rtype: iterable of
State
- to_cfg() CFG [source]¶
Turns the language L generated by this PDA when accepting on empty stack into a CFG that accepts the same language L
- Returns
new_cfg – The equivalent CFG
- Return type
- to_dict()[source]¶
Get the transitions of the PDA as a dictionary :returns: transitions – The transitions :rtype: dict
- to_empty_stack() PDA [source]¶
Turns the current PDA that accepts a language L by final state to another PDA that accepts the same language L by empty stack
- Returns
new_pda – The new PDA which accepts by empty stack the language that was accepted by final state
- Return type
- to_final_state() PDA [source]¶
Turns the current PDA that accepts a language L by empty stack to another PDA that accepts the same language L by final state
- Returns
new_pda – The new PDA which accepts by final state the language that was accepted by empty stack
- Return type
- class pyformlang.pda.StackSymbol(value)[source]¶
A StackSymbol in a pushdown automaton
- Parameters
value (any) – The value of the state
- property value¶
Returns the value of the stack symbol
- Returns
value – any
- Return type
The value