citoolkit.specifications package¶

Submodules¶

citoolkit.specifications.dfa module¶

Contains the Dfa specification class.

class citoolkit.specifications.dfa.Dfa(alphabet, states, accepting_states, start_state, transitions)[source]¶

Bases: citoolkit.specifications.spec.Spec

The Dfa class encodes a Deterministic Finite Automata specification.

Note: All state variables in all parameters can be State objects or strings. Any strings will be converted to State objects internally.

Parameters

alphabet (Set[str]) – The alphabet this Dfa is defined over.
states (Set[Union[str, State]]) – The set of all states in this Dfa.
accepting_states (Set[Union[str, State]]) – The set of all states in this Dfa that are accepting. Must be a subset of states.
start_state (Union[str, State]) – The start state in this Dfa. Must be a member of states.
transitions (Dict[Tuple[State, str], State]) – A dictionary mapping every combination of state in states and symbol in alphabet to a state in states. Must be of the form (state, symbol) -> state

Raises

ValueError – Raised if the Dfa parameters are flawed so that they do not make a well defined Dfa. I.e. the transition map is not complete.

Return type

None

accepts(word)[source]¶

Returns true if this Dfa accepts word, and false otherwise.

Parameters: word (Tuple[str, ...]) – The candidate word that is checked for belonging in the language of this Dfa.
Raises: ValueError – Raised if the word contains symbols not in this Dfa’s alphabet.
Returns: True if this Dfa accepts word and false otherwise.
Return type: bool

compute_accepting_path_counts()[source]¶

Computes the number of accepting paths from a state to an accepting state for all states.

Raises: DfaCycleError – Raised if when computing topological ordering, the Dfa is determined to by cyclical. In this case there are infinite accepting paths.
Returns: A dictionary mapping each state in the Dfa to the number of accepting paths reachable from that state.
Return type: Dict[citoolkit.specifications.dfa.State, int]

static exact_length_dfa(alphabet, length_requirement)[source]¶

Returns a Dfa that accepts all strings over alphabet with length exactly length_requirement.

Parameters

length_requirement (int) – The length of strings that the returned DFA should accept.
alphabet (Set[str]) –

Returns

A Dfa that accepts all strings over alphabet with length exactly length_requirement.

Return type

citoolkit.specifications.dfa.Dfa

static intersection_construction(dfa_a, dfa_b)[source]¶

Computes the union product construction for two DFAs and return its minimized form.

Parameters

dfa_a (citoolkit.specifications.dfa.Dfa) – The first dfa to use in the product construction.
dfa_b (citoolkit.specifications.dfa.Dfa) – The second dfa to use in the product construction.

Returns

A Dfa that accepts words accepted by dfa_a and dfa_b.

Return type

citoolkit.specifications.dfa.Dfa

language_size(min_length=None, max_length=None)[source]¶

Returns the number of words accepted by this Dfa.

Parameters

min_length (Optional[int]) – An inclusive lower bound on word size to consider.
max_length (Optional[int]) – An inclusive upper bound on word size to consider.

Raises

DfaCycleError – Raised if when computing topological ordering, the Dfa is determined to by cyclical. In this case language size is infinite.

Returns

The number of words that are in the language accepted by this Dfa, considering only words of length between min_length and max_length inclusive if defined.

Return type

int

static max_length_dfa(alphabet, length_requirement)[source]¶

Returns a Dfa that accepts all strings over alphabet with length at most length_requirement.

Parameters

length_requirement (int) – The maximum length of strings that the returned DFA should accept.
alphabet (Set[str]) –

Returns

A Dfa that accepts all strings over alphabet with length at most length_requirement.

Return type

citoolkit.specifications.dfa.Dfa

static min_length_dfa(alphabet, length_requirement)[source]¶

Returns a Dfa that accepts all strings over alphabet with length at least length_requirement.

Parameters

length_requirement (int) – The maximum length of strings that the returned DFA should accept.
alphabet (Set[str]) –

Returns

A Dfa that accepts all strings over alphabet with length at least length_requirement.

Return type

citoolkit.specifications.dfa.Dfa

minimize()[source]¶

Computes and returns a minimal Dfa that accepts the same language as self.

Returns: The complete Dfa with the smallest number of states that accepts the same language as this Dfa.
Return type: citoolkit.specifications.dfa.Dfa

negation()[source]¶

Computes and returns a Dfa that accepts words if and only if they are not accepted by self.

returns

A Dfa that accepts only words not in this Dfa’s language.

Return type: citoolkit.specifications.dfa.Dfa

sample(min_length=None, max_length=None)[source]¶

Samples a word uniformly at random from the language of this Dfa and returns the sampled word.

Parameters

min_length (Optional[int]) – An inclusive lower bound on word size to consider.
max_length (Optional[int]) – An inclusive upper bound on word size to consider.

Raises

DfaCycleError – Raised if when computing topological ordering, the Dfa is determined to by cyclical. In this case language size is infinite and so we cannot sample uniformly.

Returns

A single word sampled uniformly at random from the language of this Dfa, considering only words of length between min_length and max_length inclusive if defined.

Return type

Tuple[str, …]

states_partition()[source]¶

Uses Hopcroft’s algorithm to partition all this Dfa’s states into equivalence classes, excluding unreachable states.

Returns: A list of sets that partition the states in this Dfa into equivalence classes. For any two states in the same class and any sequence of transitions, either both states reach an accepting state on that sequence or both states reach a rejecting state on that sequence.
Return type: List[Set[citoolkit.specifications.dfa.State]]

states_topological()[source]¶

Returns a topologically sorted list of this DFA’s states, excluding those that are unreachable or dead.

Raises: DfaCycleError – Raised if when computing topological ordering, the Dfa is determined to by cyclical. In this case, a toplogical ordering is not well defined.
Returns: A topologically ordered list of states, such that no state can be transitioned to from a state later in the ordering.
Return type: List[citoolkit.specifications.dfa.State]

static union_construction(dfa_a, dfa_b)[source]¶

Computes the union product construction for two DFAs and return its minimized form.

Parameters

dfa_a (citoolkit.specifications.dfa.Dfa) – The first Dfa to use in the product construction.
dfa_b (citoolkit.specifications.dfa.Dfa) – The second Dfa to use in the product construction.

Returns

A Dfa that accepts words accepted by dfa_a or dfa_b.

Return type

citoolkit.specifications.dfa.Dfa

exception citoolkit.specifications.dfa.DfaCycleError[source]¶

Bases: Exception

An error raised when trying to compute language size for or sample from a Dfa that contains a cycle.

class citoolkit.specifications.dfa.State(*args)[source]¶

Bases: object

Class representing a state in a DFA. Primarily used for merging states and pretty printing them.

Parameters: args (*) – A sequence of strings or other State objects that will be merged into a new state.
Raises: ValueError – Raised if a non string or state object is passed in args.
Return type: None

citoolkit.specifications.spec module¶

Contains the Spec class, from which all specifications must inherit, and the AbstractSpec class, which allows one to perform the union, intersection, and negation operations on specifications.

class citoolkit.specifications.spec.AbstractSpec(spec_1, spec_2, operation)[source]¶

Bases: citoolkit.specifications.spec.Spec

The AbstractSpec class represents the language that results from a SpecOp on one or two specs.

Parameters

spec_1 (Spec) – The first specification in the operation.
spec_2 (Union[Spec, None]) – The second specificaton in the operation. In the case of a unary operation, spec_2 is None.
operation (SpecOp) – The operation to be performed on spec_1/spec_2.

Raises

ValueError – Raised if a parameter is not supported or incompatible.

Return type

None

accepts(word)[source]¶

Returns true if the specification accepts word, and false otherwise.

Parameters: word (Tuple[str, ...]) – The word which is checked for membership in the lanugage of this specification.
Raises: NotImplementedError – If an operation is passed that is not yet implemented.
Returns: True if this AbstractSpec accepts word and false otherwise.
Return type: bool

explicit()[source]¶

Computes an explicit form for this AbstractSpec, raising an exception if this is not possible.

Raises: NotImplementedError – Raised if a necessary operation is not supported for a pair of specifications.
Returns: An explicit subclass of Spec that represents the same language as this AbstractSpec.
Return type: citoolkit.specifications.spec.Spec

language_size(min_length=None, max_length=None)[source]¶

Computes the number of strings accepted by this specification. For an AbstractSpec, we first try to compute it’s explicit form, in which case we can rely on the subclasses’ counting method. Otherwise, we make as much of the AbstractSpec tree as explicit as possible, and then check if we have a “hack” to compute the size of the language anyway.

Parameters

min_length (Optional[int]) – An inclusive lower bound on word size to consider.
max_length (Optional[int]) – An inclusive upper bound on word size to consider.

Raises

NotImplementedError – Raised if there is no method to compute language size for this choice of specification and operation.

Returns

The size of the language accepted by this AbstractSpec.

Return type

int

sample(min_length=None, max_length=None)[source]¶

Samples uniformly at random from the language of this specification. For an AbstractSpec, we first try to compute it’s explicit form, in which case we can rely on the subclasses’ sample method. Otherwise, we make as much of the AbstractSpec tree as explicit as possible, and then check if we have a “hack” to sample from the language anyway.

Parameters

min_length (Optional[int]) – An inclusive lower bound on word size to consider.
max_length (Optional[int]) – An inclusive upper bound on word size to consider.

Raises

NotImplementedError – Raised if there is no method to sample uniformly from this choice of specification and operation.

Returns

A uniformly sampled word from the language of this AbstractSpec.

Return type

Tuple[str, …]

class citoolkit.specifications.spec.Spec(alphabet)[source]¶

Bases: abc.ABC

The Spec class is a parent class to all specifications.

Parameters: alphabet (Set[str]) – The alphabet this specification is defined over.
Return type: None

abstract accepts(word)[source]¶

Returns true if the specification accepts word, and false otherwise.

Parameters: word (Tuple[str, ...]) – The word which is checked for membership in the lanugage of this specification.
Returns: True if this Spec accepts word and false otherwise.
Return type: bool

abstract language_size(min_length=None, max_length=None)[source]¶

Computes the number of strings accepted by this specification.

Parameters

min_length (Optional[int]) – An inclusive lower bound on word size to consider.
max_length (Optional[int]) – An inclusive upper bound on word size to consider.

Returns

The size of the language accepted by this Spec.

Return type

int

abstract sample(min_length=None, max_length=None)[source]¶

Generate a word uniformly at random from this specification.

Parameters

min_length (Optional[int]) – An inclusive lower bound on word size to consider.
max_length (Optional[int]) – An inclusive upper bound on word size to consider.

Returns

A uniformly sampled word from the language of this Spec.

Return type

Tuple[str, …]

class citoolkit.specifications.spec.SpecOp(value)[source]¶

Bases: enum.Enum

An enum enconding the different operations that can be performed on specifications.

INTERSECTION = 2¶

NEGATION = 3¶

UNION = 1¶

citoolkit.specifications package¶

Submodules¶

citoolkit.specifications.dfa module¶

citoolkit.specifications.spec module¶

Module contents¶