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

An epsilon symbol

class pyformlang.pda.PDA(states: AbstractSet[Any] = None, input_symbols: AbstractSet[Any] = None, stack_alphabet: AbstractSet[Any] = None, transition_function: TransitionFunction = None, start_state: Any = None, start_stack_symbol: Any = None, final_states: AbstractSet[Any] = None)

Representation of a pushdown automaton

Parameters:

statesset of State, optional

A finite set of states

input_symbolsset of Symbol, optional

A finite set of input symbols

stack_alphabetset of StackSymbol, optional

A finite stack alphabet

transition_functionTransitionFunction, 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_stateState, optional

A start state, element of states

start_stack_symbolStackSymbol, optional

The stack is initialized with this stack symbol

final_statesset of State, optional

A set of final or accepting states. It is a subset of states.

add_final_state(state: Any)

Adds a final state to the automaton

Parameters:

stateState

The state to add

add_transition(s_from: Any, input_symbol: Any, stack_from: Any, s_to: Any, stack_to: Iterable[Any])

Add a transition to the PDA

Parameters:

s_fromState

The starting symbol

input_symbolSymbol

The input symbol for the transition

stack_fromStackSymbol

The stack symbol of the transition

s_toState

The new state

stack_tolist of StackSymbol

The string of stack symbol which replace the stack_from

add_transitions(transitions)

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)

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:

pda

A PDA automaton read from the graph

get_number_transitions() → int

Gets the number of transitions in the PDA

Returns:

n_transitionsint

The number of transitions

property input_symbols

The input symbols of the PDA

Returns:

input_symbolsiterable of Symbol

The input symbols of the PDA

intersection(other: Any) → PDA

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:

otherany

The other part of the intersection

Returns:

new_pdaPDA

The pda resulting of the intersection

Raises:

NotImplementedError

When intersecting with something else than a regex or a finite automaton

set_start_stack_symbol(start_stack_symbol: Any)

Sets the start stack symbol to the automaton

Parameters:

start_stack_symbolStackSymbol

The start stack symbol

set_start_state(start_state: Any)

Sets the start state to the automaton

Parameters:

start_stateState

The start state

property stack_symbols

The stack symbols of the PDA

Returns:

stack_symbolsiterable of StackSymbol

The stack symbols of the PDA

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

Turns the language L generated by this PDA when accepting on empty stack into a CFG that accepts the same language L

Returns:

new_cfgCFG

The equivalent CFG

to_dict()

Get the transitions of the PDA as a dictionary :returns: transitions – The transitions :rtype: dict

to_empty_stack() → PDA

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_pdaPDA

The new PDA which accepts by empty stack the language that was accepted by final state

to_final_state() → PDA

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_pdaPDA

The new PDA which accepts by final state the language that was accepted by empty stack

to_networkx() → MultiDiGraph

Transform the current pda into a networkx graph

Returns:

graphnetworkx.MultiDiGraph

A networkx MultiDiGraph representing the pda

write_as_dot(filename)

Write the PDA in dot format into a file

Parameters:

filenamestr

The filename where to write the dot file

class pyformlang.pda.StackSymbol(value)

A StackSymbol in a pushdown automaton

Parameters:

valueany

The value of the state

property value

Returns the value of the stack symbol

Returns:

value: The value

any

class pyformlang.pda.State(value)

A State in a pushdown automaton

Parameters:

valueany

The value of the state

property value

Returns the value of the state

Returns:

value: The value

any

class pyformlang.pda.Symbol(value)

A Symbol in a pushdown automaton

Parameters:

valueany

The value of the state

property value

Returns the value of the symbol

Returns:

value: The value

any