Misc Language Operators

Project

Natural projection of marked and generated language.

Detailed description:

Given two alphabets Sigma and Sigma0, Sigma0 ⊆ Sigma, the natural projection P0:Sigma*→Sigma0* maps strings s ∈ Sigma* to strings r ∈ Sigma0* by cancelling any symbols o ∉ Sigma0:

P0(epsilon) = epsilon
P0(so) = P0(s)     if o ∉ Sigma0
P0(so) = P0(s)o     if o ∈ Sigma0

The function Project constructs a generator GRes that realises the projection of the marked and generated languages specified by the argument G:

L(GRes) = P0(L(G))
Lm(GRes) = P0(Lm(G))

The implementation iteratively replaces transitions with labels o ∉ Sigma0 by transitions to the next successor states. In general, this will lead to a non-deterministic generator. The function Project therefore subsequently calls Deterministic and StateMin to construct a deterministic realisation of the result.

As of libFAUDES 2.23f, alternative implementations are provided via the C++ API. Please let us know, if you experience performance issues with the default algorithm.

Example:

G GRes with Project(G, {a, c, g, e}, GRes)

Parameter Conditions:

The specified generator does not need to be deterministic. The resulting generator is deterministic.

InvProject

Inverse projection of marked and generated language.

Detailed description:

Given two alphabets Sigma and Sigma0, Sigma0 ⊆ Sigma, the set-valued inverse of the natural projection Pinv0 maps strings r ∈ Sigma0* to sets of strings Pinv0(r) ⊆ Sigma* by inserting arbitrary symbols o ∉ Sigma0:

Pinv0(r) = {s ∈ Sigma*| P0(s) = r}    for r ∈ Sigma0*,

see also Project.

The function InvProject constructs a generator GRes that realises the inverse projection of the marked and generated languages specified by the argument G0:

L(GRes) = Pinv0(L(G0))
Lm(GRes) = Pinv0(Lm(G0))

This implementation realises the inverse projection by inserting self-loop transitions at every state for all events that are in the target alphabet Sigma but not in the generators alphabet Sigma0.

Parameter Conditions:

The target alphabet Sigma must be a superset of the generators alphabet. Provided the specified generator is deterministic, so is the resulting generator.

SelfLoop

Self loop with specified alphabet.

Detailed description:

This function self-loops all states of the provide generator G with the events from the alphabet Sigma: for each state q ∈ G and each event o ∈ Sigma, a transition (q,o,q) is inserted, irrespective of whether this event was already active in q before.

Parameter Conditions:

The provided generator may be non-deterministic. When a deterministic generator is provided, the result can still become non-deterministic in the case that Sigma shares events with the original alphabet.