Misc Functions on Generators

EmptyLanguage

Set generator to mark empty language.

Detailed description:

Returns a generator G with the specified alphabet Sigma, no states and no transitions; i.e., we have Lm(G) = L(G) = 0.

Parameter Conditions:

The empty language generator is deterministic.

IsEmptyLanguage

Test Generator G for empty marked language Lm(G).

Parameter Conditions:

The argument may be non-deterministic.

Automaton

Convert generator to formal automaton.

Detailed description:

Converts the given generator G to a formal automaton that generates the same marked language Lm(G) while accepting any input string, i.e. L(G) = Sigma*. This is achieved by introducing a dump state to represent Sigma*-Closure(Lm(G)).

Example:

G GRes

Parameter Conditions:

The provided generator is assumed to be deterministic. The resulting generator is guaranteed to be deterministic.

IsClosed

Tests a language for being prefix-closed.

Detailed description:

A language L is prefix-closed if for each string s ∈ L all prefixes r ≤ s are also element of L:

s ∈ L and r ≤ s    ⇒    r ∈ L.

The function IsClosed tests whether the language Lm(G) marked by the specified generator G is prefix-closed. It does so by testing whether any state that is accessible and co-accessible also is marked. For deterministic generators, this condition is sufficient and necessary. In general, it is only sufficient.

Example:

G

The language Lm(G) marked by the above generator is not prefix-closed, since the states 1, 2 and 4 are accessible and co-accessible but not marked. For example, the string ac ∉ Lm(G) is a prefix of acbb ∈ Lm(G).

PrefixClosure

Compute prefix closure for given language.

Detailed description:

For any language L there exists a smallest prefix-closed superset, the so-called prefix-closure of L:

Closure(L) := {r ∈ Sigma*| ∃ s ∈ L : r ≤ s}.

This function computes a realisation of the prefix-closure of Lm(GArg) by first erasing all states that are not co-accessible and then marking the remaining states.

Example:

G GRes