FAdo.transducers

Finite Tranducer Support

Transducer manipulation.

New in version 1.0.

class GFT

General Form Transducer

addOutput(sym)

Add a new symbol to the output alphabet

There is no problem with duplicate symbols because Output is a Set. No symbol Epsilon can be added

Parameters:

sym (str) – symbol or regular expression to be added

addTransition(stsrc, wi, wo, sti2)

Adds a new transition

Parameters:

• stsrc (int) – state index of departure

• sti2 (int) – state index of arrival

• wi (str) – word consumed

• wo (str) – word outputed

codeOfTransducer()

Appends into one string the codes of the alphabets and initial and final state sets and the set of transitions

Return type:

tuple

listOfTransitions()

Collects into a sorted list the transitions of the transducer.

Return type:

set of tuples

toSFT()

Conversion to an equivalent SFT

rtype: SFT

class NFT

Normal Form Transducer.

Transsitions here have labels of the form (s,Epsilon) or (Epsilon,s)

class SFT

Standard Form Tranducer

Variables:

Output (set) – output alphabet

addEpsilonLoops()

Add a loop transition with epsilon input and output to every state in the transducer.

addTransition(stsrc, symi, symo, sti2)

Adds a new transition

Parameters:

• stsrc (int) – state index of departure

• sti2 (int) – state index of arrival

• symi (str) – symbol consumed

• symo (str) – symbol output

addTransitionProductQ(src, dest, ddest, sym, out, futQ, pastQ)

Add transition to the new transducer instance.

Version for the optimized product

Parameters:

• src – source state

• dest – destination state

• ddest – destination as tuple

• sym – symbol

• out – output

• futQ (set) – queue for later

• pastQ (set) – past queue

addTransitionQ(src, dest, sym, out, futQ, pastQ)

Add transition to the new transducer instance.

Parameters:

• src – source state

• dest – destination state

• sym – symbol

• out – output

• futQ (set) – queue for later

• pastQ (set) – past queue

composition(other)

Composition operation of a transducer with a transducer.

Parameters:

other (SFT) – the second transducer

Return type:

SFT

concat(other)

Concatenation of transducers

Parameters:

other (SFT) – the other operand

Return type:

SFT

delTransition(sti1, sym, symo, sti2, _no_check=False)

Remove a transition if existing and perform cleanup on the transition function’s internal data structure.

Parameters:

• symo – symbol output

• sti1 (int) – state index of departure

• sti2 (int) – state index of arrival

• sym – symbol consumed

• _no_check (bool) – dismiss secure code

deleteState(sti)

Remove given state and transitions related with that state.

Parameters:

sti (int) – index of the state to be removed

Raises:

DFAstateUnknown – if state index does not exist

deleteStates(lstates)

Delete given iterable collection of states from the automaton.

Parameters:

lstates (set|list) – collection of int representing states

dup()

Duplicate of itself :rtype: SFT

Attention

only duplicates the initially connected component

emptyP()

Tests if the relation realized the empty transducer

Return type:

bool

epsilonOutP()

Tests if epsilon occurs in transition outputs

Return type:

bool

epsilonP()

Test whether this transducer has input epsilon-transitions

Return type:

bool

evalWordP(wp)

Tests whether the transducer returns the second word using the first one as input

Parameters:

wp (tuple) – pair of words

Return type:

bool

evalWordSlowP(wp)

Tests whether the transducer returns the second word using the first one as input

Note: original :param tuple wp: pair of words :rtype: bool

functionalP()

Tests if a transducer is functional using Allauzer & Mohri and Béal&Carton&Prieur&Sakarovitch algorithms.

Return type:

bool

See also

Cyril Allauzer and Mehryar Mohri, Journal of Automata Languages and Combinatorics, Efficient Algorithms for Testing the Twins Property, 8(2): 117-144, 2003.

See also

M.P. Béal, O. Carton, C. Prieur and J. Sakarovitch. Squaring transducers: An efficient procedure for deciding functionality and sequentiality. Theoret. Computer Science 292:1 (2003), 45-63.

Note

This is implemented using nonFunctionalW()

inIntersection(other)

Conjunction of transducer and automata: X & Y.

Note

This is a fast version of the method that does not produce meaningfull state names.

Note

The resulting transducer is not trim.

Parameters:

other (DFA|NFA) – the automata needs to be operated.

Return type:

SFT

inIntersectionSlow(other)

Conjunction of transducer and automata: X & Y.

Note

This is the slow version of the method that keeps meaningfull names of states.

Parameters:

other (DFA|NFA) – the automata needs to be operated.

Return type:

SFT

inverse()

Switch the input label with the output label.

No initial or final state changed.

Returns:

Transducer with transitions switched.

Return type:

SFT

nonEmptyW()

Witness of non emptyness

Returns:

pair (in-word, out-word)

Return type:

tuple

nonFunctionalW()

Returns a witness of non funcionality (if is that the case) or a None filled triple

Returns:

witness

Return type:

tuple

outIntersection(other)

Conjunction of transducer and automaton: X & Y using output intersect operation.

Parameters:

other (DFA|NFA) – the automaton used as a filter of the output

Return type:

SFT

outIntersectionDerived(other)

Naive version of outIntersection

Parameters:

other (DFA|NFA) – the automaton used as a filter of the output

Return type:

SFT

outputS(s)

Output label coming out of the state i

Parameters:

s (int) – index state

Return type:

set

productInput(other)

Returns a transducer (skeleton) resulting from the execution of the transducer with the automaton as filter on the input.

Note

This version does not use stateIndex() with the price of generating some unreachable sates

Parameters:

other (NFA) – the automaton used as filter

Return type:

SFT

Changed in version 1.3.3.

productInputSlow(other)

Returns a transducer (skeleton) resulting from the execution of the transducer with the automaton as filter on the input.

Note

This is the slow version of the method that keeps meaningfull names of states.

Parameters:

other (NFA) – the automaton used as filter

Return type:

SFT

reversal()

Returns a transducer that recognizes the reversal of the relation.

Returns:

Transducer recognizing reversal language

Return type:

SFT

runOnNFA(nfa)

Result of applying a transducer to an automaton

Parameters:

nfa (DFA|NFA) – input language to transducer

Returns:

resulting language

Return type:

NFA

runOnWord(word)

Returns the automaton accepting the outup of the transducer on the input word

Parameters:

word – the word

Return type:

NFA

setInitial(sts)

Sets the initial state of a Transducer

Parameters:

sts (list) – list of states

square()

Conjunction of transducer with itself

Return type:

NFA

square_fv()

Conjunction of transducer with itself (Fast Version)

Return type:

NFA

star(flag=False)

Kleene star

Parameters:

flag (bool) – plus instead of star

Returns:

the resulting Transducer

Return type:

SFT

toInNFA()

Delete the output labels in the transducer. Translate it into an NFA

Return type:

NFA

toNFT()

Transformation into Nomal Form Transducer

Return type:

NFT

toOutNFA()

Returns the result of considering the output symbols of the transducer as input symbols of a NFA (ignoring the input symbol, thus)

Returns:

the NFA

Return type:

NFA

toSFT()

Pacifying rule

Return type:

SFT

trim()

Remove states that do not lead to a final state, or, inclusively, that can’t be reached from the initial state. Only useful states remain.

Attention

in place transformation

union(other)

Union of the two transducers

Parameters:

other (SFT) – the other operand

Return type:

SFT

class Transducer

Base class for Transducers

setOutput(listOfSymbols)

Set Output

Parameters:

listOfSymbols (set|list) – output symbols

succintTransitions()

Collects the transition information in a concat way suitable for graphical representation. :rtype: list of tupples

exception ZERO

Simple exception for functionality testing algorithm

concatN(x, y)

Concatenation of tuples of words :param x: iterable :param y: iterable :return: iterable

hypercodeTransducer(alphabet, preserving=False)

Creates an hypercode property transducer based on given alphabet

Parameters:

• preserving (bool) – input preserving transducer, else input altering

• alphabet (list|set) – alphabet

Return type:

SFT

infixTransducer(alphabet, preserving=False)

Creates an infix property transducer based on given alphabet

Parameters:

• preserving (bool) – input preserving transducer, else input altering

• alphabet (list|set) – alphabet

Return type:

SFT

isLimitExceed(NFA0Delta, NFA1Delta)

Decide if the size of NFA0 and NFA1 exceed the limit.

Size of NFA0 is denoted as N, and size of NFA1 is denoted as M. If N*N*M exceeds 1000000, return False, else return True. If bothNFA is False, then NFA0 should be NFA, and NFA1 should be Transducer. If both NFA is True, then NFA0 and NFA1 are both NFAs.

Parameters:

• NFA0Delta (dict) – NFA0’s transition Delta

• NFA1Delta (dict) – NFA1’s transition Delta

Return type:

bool

outfixTransducer(alphabet, preserving=False)

Creates an outfix property transducer based on given alphabet

Parameters:

• preserving (bool) – input preserving transducer, else input altering

• alphabet (list|set) – alphabet

Return type:

SFT

prefixTransducer(alphabet, preserving=False)

Creates an prefix property transducer based on given alphabet

Parameters:

• preserving (bool) – input preserving transducer, else input altering

• alphabet (list|set) – alphabet

Return type:

SFT

suffixTransducer(alphabet, preserving=False)

Creates an suffix property transducer based on given alphabet

Parameters:

• preserving (bool) – input preserving transducer, else input altering

• alphabet (list|set) – alphabet

Return type:

SFT