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.Epsilon[source]

An 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 states

  • input_symbols (set of Symbol, optional) – A finite set of input symbols

  • stack_alphabet (set of StackSymbol, optional) – A finite stack alphabet

  • transition_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 X

  • start_state (State, optional) – A start state, element of states

  • start_stack_symbol (StackSymbol, optional) – The stack is initialized with this stack symbol

  • final_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 symbol

  • input_symbol (Symbol) – The input symbol for the transition

  • stack_from (StackSymbol) – The stack symbol of the transition

  • s_to (State) – The new state

  • stack_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

int

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

PDA

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

CFG

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

PDA

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

PDA

to_networkx() → MultiDiGraph[source]

Transform the current pda into a networkx graph

Returns

graph – A networkx MultiDiGraph representing the pda

Return type

networkx.MultiDiGraph

write_as_dot(filename)[source]

Write the PDA in dot format into a file

Parameters

filename (str) – The filename where to write the dot file

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

class pyformlang.pda.State(value)[source]

A State in a pushdown automaton

Parameters

value (any) – The value of the state

property value

Returns the value of the state

Returns

value – any

Return type

The value

class pyformlang.pda.Symbol(value)[source]

A Symbol in a pushdown automaton

Parameters

value (any) – The value of the state

property value

Returns the value of the symbol

Returns

value – any

Return type

The value