FAdo.conversions

Conversions between objects.

Deterministic and non-deterministic automata manipulation, conversion and evaluation. .. Authors: Rogério Reis & Nelma Moreira .. This is part of FAdo project https://fado.dcc.fc.up.pt.

DFA2regexpDijkstra(aut) → RegExp[source]

Returns a regexp for the current DFA considering the recursive method. Very inefficent.

Parameters:

aut (DFA) – the automaton

Returns:

a regexp equivalent to the current DFA

Return type:

reex.RegExp

DFAsyncWords(aut)[source]

Evaluates the regular expression corresponding to the synchronizing pwords of the automata.

Parameters:

aut (DFA) – the automata

Returns:

a regular expression of the sync words of the automata

Return type:

reex.RegExp

FA2GFA(aut)[source]

Creates a GFA equivalent to NFA

Parameters:

aut (OFA) – the automaton

Returns:

deep copy

Return type:

GFA

FA2regexpCG(aut)[source]

Regular expression from state elimination whose language is recognised by the FA. Uses a heuristic to choose the order of elimination.

Parameters:

aut (OFA) – the automaton

Returns:

the equivalent regular expression

Return type:

reex.RegExp

FA2regexpCG_nn(aut: OFA)[source]

Regular expression from state elimination whose language is recognised by the FA. Uses a heuristic to choose the order of elimination. The FA is not normalized before the state elimination.

Parameters:

aut (OFA) – the automaton

Returns:

the equivalent regular expression

Return type:

reex.RegExp

FA2regexpDynamicCycleHeuristic(aut)[source]

State elimination Heuristic based on the number of cycles that passes through each state. Here those numbers are evaluated dynamically after each elimination step

Parameters:

aut (OFA) – the automaton

Returns:

an equivalent regular expression

Return type:

reex.RegExp

See also

Nelma Moreira, Davide Nabais, and Rogério Reis. State elimination ordering strategies: Some experimental results. Proc. of 11th Workshop on Descriptional Complexity of Formal Systems (DCFS10), pages 169-180.2010. DOI: 10.4204/EPTCS.31.16

FA2regexpSE(aut)[source]

A regular expression obtained by state elimination algorithm whose language is recognised by the FA aut.

Parameters:

aut (OFA) – the automaton

Returns:

the equivalent regular expression

Return type:

reex.RegExp

FA2regexpSEO(aut, order=None)[source]

Regular expression from state elimination whose language is recognised by the FA. The FA is normalized before the state elimination.

Parameters:

  • aut (OFA) – the automaton

  • order (list) – state elimination sequence

Returns:

the equivalent regular expression

Return type:

reex.RegExp

FA2regexpSE_nn(aut, order=None)[source]

Regular expression from state elimination whose language is recognised by the FA. The FA is not normalized before the state elimination.

Parameters:

  • aut (OFA) – the automaton

  • order (list) – state elimination sequence

Returns:

the equivalent regular expression

Return type:

reex.RegExp

FA2regexpStaticCycleHeuristic(aut)[source]

State elimination Heuristic based on the number of cycles that passes through each state. Here those numbers are evaluated statically in the beginning of the process

Parameters:

aut (OFA) – the automaton

Returns:

a equivalent regular expression

Return type:

reex.RegExp

See also

Nelma Moreira, Davide Nabais, and Rogério Reis. State elimination ordering strategies: Some experimental results. Proc. of 11th Workshop on Descriptional Complexity of Formal Systems (DCFS10), pages 169-180.2010. DOI: 10.4204/EPTCS.31.16

FAallRegExps(aut)[source]

Evaluates the alphabetic length of the equivalent regular expression using every possible order of state elimination.

Parameters:

aut (OFA) – the automaton

Returns:

list of tuples (int, list of states)

Return type:

listo of tuples

FAeliminateSingles(aut)[source]

Eliminates every state that only have one successor and one predecessor.

Parameters:

aut (OFA) – the automaton

Returns:

GFA after eliminating states

Return type:

GFA

class GFA[source]

Class for Generalized Finite Automata: NFA with a unique initial state and transitions are labeled with RegExp.

Inheritance diagram of GFA
DFS(io)[source]

Depth first search

Parameters:

io –

addTransition(sti1, sym, sti2)[source]
Adds a new transition from sti1 to sti2 consuming symbol sym. Label of the transition function

is a RegExp.

Parameters:

  • sti1 (int) – state index of departure

  • sti2 (int) – state index of arrival

  • sym (str) – symbol consumed

Raises:

DFAepsilonRedefenition – if sym is Epsilon

assignLow(st)[source]
Parameters:

st –

assignNum(st)[source]
Parameters:

st –

completeDelta()[source]

Adds empty set transitions between the automatons final and initial states in order to make it complete. It’s only meant to be used in the final stage of SEA…

deleteState(sti)[source]

deletes a state from the GFA :param sti:

dfs_visit(s, visited, io)[source]
Parameters:

  • s – state

  • visited – list od states visited

  • io –

dup()[source]

Returns a copy of a GFA

Return type:

GFA

eliminate(st)[source]

Eliminate a state.

Parameters:

st (int) – state to be eliminated

eliminateAll(lr)[source]

Eliminate a list of states.

Parameters:

lr (list) – list of states indexes

eliminateState(st)[source]

Deletes a state and updates the automaton

Parameters:

st (int) – the state to be deleted

evalNumberOfStateCycles()[source]

Evaluates the number of cycles each state participates

Returns:

state->list of cycle lengths

Return type:

dict

evalSymbol(stil, sym)[source]

Eval symbol

normalize()[source]

Create a single initial and final state with Epsilon transitions.

Attention

works in place

reorder(dictio)[source]

Reorder states indexes according to given dictionary.

Parameters:

dictio (dict) – order

Note

dictionary does not have to be complete

stateChildren(state, strict=False)[source]

Set of children of a state

Parameters:

  • strict (bool) – a state is never its own children even if a self loop is in place

  • state (int) – state id queried

Returns:

map: children -> alphabetic length

Return type:

dictionary

succintTransitions()[source]

Collapsed transitions

weight(state)[source]

Calculates the weight of a state based on a heuristic

Parameters:

state (int) – state

Returns:

the weight of the state

Return type:

int

weightWithCycles(state, cycles)[source]
Parameters:

  • state –

  • cycles –

Returns:

SP2regexp(aut)[source]

Checks if FA is SP (Serial-PArallel), and if so returns the regular expression whose language is recognised by the FA

Parameters:

aut (OFA) – the automaton

Returns:

equivalent regular expression

Return type:

reex.RegExp

Raises:

NotSP – if the automaton is not Serial-Parallel

See also

Moreira & Reis, Fundamenta Informatica, Series-Parallel automata and short regular expressions, n.91 3-4, pag 611-629. https://www.dcc.fc.up.pt/~nam/publica/spa07.pdf

Note

Automata must be Serial-Parallel

cutPoints(aut)[source]

Set of FA’s cut points

Parameters:

aut (OFA) – the automaton

Return type:

set of states