Recursive State Automaton

pyformlang.rsa

This module deals with recursive automaton.

References

[1] Alur R., Etessami K., Yannakakis M. (2001) Analysis of Recursive State Machines. In: Berry G., Comon H., Finkel A. (eds) Computer Aided Verification. CAV 2001. Lecture Notes in Computer Science, vol 2102. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44585-4_18

Available Classes

RecursiveAutomaton

A recursive automaton

Box

A constituent part of a recursive automaton

class pyformlang.rsa.Box(enfa: EpsilonNFA, nonterminal: Symbol | str)[source]

Represents a box for recursive automaton

This class represents a box for recursive automaton

Parameters:
enfaEpsilonNFA

A epsilon nfa

nonterminalSymbol

A nonterminal for epsilon nfa

property dfa

Box’s dfa

property final_states

The final states

is_equivalent_to(other)[source]

Check whether two boxes are equivalent

Parameters:
otherBox

A sequence of input symbols

Returns:
are_equivalentbool

Whether the two boxes are equivalent or not

property nonterminal

Box’s nonterminal

property start_states

The start states

to_subgraph_dot()[source]

Creates a named subgraph representing a box

class pyformlang.rsa.RecursiveAutomaton(start_box: Box, boxes: AbstractSet[Box])[source]

Represents a recursive automaton

This class represents a recursive automaton.

Parameters:
start_boxBox

Start box

boxesset of Box

A finite set of boxes

property boxes: dict

The set of boxes

classmethod from_ebnf(text, start_nonterminal: Symbol | str = S)[source]

Create a recursive automaton from ebnf (ebnf = Extended Backus-Naur Form)

Parameters:
textstr

The text of transform

start_nonterminalSymbol | str, optional

The start nonterminal, S by default

Returns:
rsaRecursiveAutomaton

The new recursive automaton built from context-free grammar

classmethod from_regex(regex: Regex, start_nonterminal: Symbol | str)[source]

Create a recursive automaton from regular expression

Parameters:
regexRegex

The regular expression

start_nonterminalSymbol | str

The start nonterminal for the recursive automaton

Returns:
rsaRecursiveAutomaton

The new recursive automaton built from regular expression

get_box_by_nonterminal(nonterminal: Symbol | str)[source]

Box by nonterminal

Parameters:
nonterminal: :class:`~pyformlang.finite_automaton.Symbol` | str

the nonterminal of which represents a box

Returns:
boxBox | None

box represented by given nonterminal

get_number_boxes()[source]

Size of set of boxes

is_equals_to(other)[source]

Check whether two recursive automata are equals by boxes. Not equivalency in terms of formal languages theory, just mapping boxes

Parameters:
otherRecursiveAutomaton

The input recursive automaton

Returns:
are_equivalentbool

Whether the two recursive automata are equals or not

property nonterminals: set

The set of nonterminals

property start_box

The start box

property start_nonterminal: Symbol

The start nonterminal

to_dot()[source]

Create dot representation of recursive automaton