Finite Transducers ⬩ Adamátorovy zápisky

Definition

A finite automaton on

A

is a directed graph with edges labelled by the letters from

A

. It is described by the 5-tuple

𝒜 = ⟨ A, Q, I, E, T ⟩

, where

Q

is the set of states (vertices),

I \subset Q

is the set of initial states,

E \subset Q \times A \times Q

is the set of transitions and

T \subset Q

is the set of final states. The accepted language is the set

L (𝒜) ≔ {w \in A^{*} | \exists i \in I, t \in T : i \to_{𝒜}^{w} t} .

Note

Let

A^{*}, B^{*}

be two free monoids. Then

A^{*} \times B^{*}

is also a monoid, but not free (for example, given

a \in A

and

b \in B

, the elements

(a, 1_{A^{*}})

and

(1_{B^{*}}, b)

commute).

Definition

A finite transducer on

A

is a directed graph with edges labelled by pairs from

A^{*} \times B^{*}

. It is described by the 5-tuple

𝒯 = ⟨ A^{*} \times B^{*}, Q, I, E, T ⟩

, where

Q

is the set of states (vertices),

I \subset Q

is the set of initial states,

E \subset Q \times A^{*} \times B^{*} \times Q

is the set of transitions and

T \subset Q

is the set of final states. We define

| 𝒯 | ≔ {(u, v) | \exists i \in I, t \in T : i \to_{𝒯}^{(u, v)} T} .

Definition

A relation

θ

from

A^{*}

B^{*}

is defined by its graph

\hat{θ} \subset A^{*} \times B^{*}

and denoted by

θ : A^{*} \to B^{*}

, with

θ (u) ≔ {v \in B^{*} | (u, v) \in \hat{θ}} .

Its inverse is

θ^{- 1} : B^{*} \to A^{*}

with the same graph and

θ^{- 1} (v) ≔ {u \in A^{*} | (u, v) \in \hat{θ}} .

Definition additivity

Let

L \subset A^{*}

. Then

θ (L) ≔ ⋃_{u \in L} θ (u)

Definition

The complement of a relation

θ

is the relation

∁ θ

such that

\hat{∁ θ} = ∁ \hat{θ} = (A^{*} \times B^{*}) ∖ \hat{θ}

Definition

Let

𝒯

be a finite transducer. Then

| 𝒯 |

is its realised relation.

Note

The domain and range of

| 𝒯 |

are regular languages and the relation

{| 𝒯 |}^{- 1}

is also realised by a transducer (with the labels swapped).

Note

C ≔ (A \times {1}) \cup ({1} \times B)

is a generating set of the monoid

A^{*} \times B^{*}

. So is

D ≔ (A \times {1}) \cup ({1} \times B) \cup (A \times B)

Definition

A transducer is normalised if its labels are in

C

and subnormalised if its labels are in

D

Theorem

Every transducer is equivalent to a normalised transducer.

(u, v)

Definition

An automaton over a monoid

M

is proper if no edge is labelled by

1_{M}

(spontaneous transition).

Theorem

Every automaton is equivalent to a proper automaton.

Proof Shown in the main lecture . It uses the backward closure and the forward closure .

Definition

Let

K \subset A^{*}

be a regular language. We define the relation

z_{K} : A^{*} \to A^{*}

z_{K} (u) ≔ {\begin{cases} {u} & if u \in K, \\ \emptyset & otherwise. \end{cases}

Note Obviously this relation is accepted by a finite transducer.

Note

We can extend the notion of a finite transducer to arbitrarily many free monoids.

Note

We can also have right automata, which read from right to left. We can model a right automaton as the transpose of a left automaton. However, this does not preserve certain properties (such as determinism), so it is often useful to treat them as a separate concept.

Definition

The composition of relations

θ : A^{*} \to B^{*}

and

σ : B^{*} \to C^{*}

is the relation

σ \circ θ : A^{*} \to C^{*}

defined as

(σ \circ θ) (u) ≔ σ (θ (u))

, or equivalently

\hat{σ \circ θ} ≔ {(u, w) \in A^{*} \times C^{*} | \exists v \in B^{*} : (u, v) \in \hat{θ} \land (v, w) \in \hat{σ}} .

Definition

The composition product of two subnormalised transducers

𝒯 = ⟨ A^{*} \times B^{*}, Q, I, E, T ⟩, 𝒮 = ⟨ B^{*} \times C^{*}, R, J, F, U ⟩

is the transducer

𝒯 ⋈ 𝒮 = ⟨ A^{*} \times C^{*}, Q \times R, I \times J, G, T \times U ⟩

with

G ≔ G_{1} \cup G_{2} \cup G_{3}

G_{1} ≔ {(p, r) \overset{(x, y)}{\to} (q, s) | x \in A \cup {1}, y \in C \cup {1}, p, q \in Q, r, s \in R | \exists b \in B : p \overset{(a, b)}{\to} q \in E \land r \overset{(b, y)}{\to} s \in F},

G_{2} ≔ {(p, r) \overset{(a, 1)}{\to} (q, r) | a \in A, p, q \in Q, r \in R | p \overset{(a, 1)}{\to} q \in E},

G_{3} ≔ {(p, r) \overset{(1, c)}{\to} (p, s) | c \in C, p \in Q, r, s \in R | r \overset{(1, c)}{\to} s \in E} .

Note The composition product might result in spontaneous transitions, which can be eliminated with backward closure.

Theorem Elgot-Megei

The relation realised by the composition product of two transducers is the composition of their relations.

Note

Let

M

be a monoid. Then

𝒫 (M)

with the operations

\cup, \cdot

is a semiring.

Definition

Let

M

be a monoid and

P \subset M

. Then we define

P^{0} ≔ {1_{M}}, P^{n + 1} ≔ P^{n} \cdot P, P^{*} ≔ ⋃_{n \in ℕ_{0}} P^{n}

Lemma

Let

M

be a monoid and

P \subset M

. Then

P^{*} = ⟨ P ⟩

Definition

A rational expression over a monoid

M

is an expression built inductively as:

$0$ , $1$ and $m \in M$ are atomic expressions,
if $E, F$ are expressions, then $E + F$ , $E \cdot F$ and $E^{*}$ are expressions.

The subset denoted by a rational expression is

$| 0 | = \emptyset, | 1 | = {1_{M}}, | m | = {m},$
$| E + F | = | E | \cup | F |,$
$| E \cdot F | = | E | | F |,$
$| E^{*} | = {| E |}^{*} .$

A subset

P \subset M

is rational if it is denoted by a rational expression. The set of all rational subsets is denoted

Rat M

X^{*} = 1 + X X^{*}

Theorem

A subset of a monoid

M

is rational if and only if it is accepted by a finite automaton over

M

Proof Analogous to the one for regular languages. (\Rightarrow) Operations on standard automata. (\Leftarrow) State elimination method.

Note

Unlike regular languages, rational sets are not closed under intersection. For example, let

| 𝒱_{1} | ≔ {(𝖺^{n} 𝖻^{m}, 𝖼^{n}) | n, m \in ℕ},

| 𝒱_{2} | ≔ {(𝖺^{n} 𝖻^{m}, 𝖼^{m}) | n, m \in ℕ} .

Both of these can be recognised by a finite transducer, but their intersection is

| 𝒱_{1} | \cap | 𝒱_{2} | = {(𝖺^{n} 𝖻^{n}, 𝖼^{n}) | n \in ℕ},

which is clearly not rational.

Corollary Rational sets are not closed under complement.

Theorem

The complement if the identity is a rational expression.

θ

Theorem Rabin & Scott, 1959

Given

R, S \in Rat A^{*} \times B^{*}

with

| A |, | B | \geq 2

, it is undecidable whether

R \cap S = \emptyset

Theorem Fischer & Rosenberg, 1968

| A |, | B | \geq 2

, it is undecidable whether two transducers over

A^{*} \times B^{*}

are equivalent.

Theorem Gibbons & Ryther, 1986

Given

R, S \in Rat {𝖺, 𝖻}^{*} \times {𝖼}

, it is decidable whether

R \cap S = \emptyset

Theorem Ibarra, 1978; Liskovik, 1979

It is undecidable whether two transducers over

{𝖺, 𝖻}^{*} \times {𝖼}

are equivalent.

Problem Post correspondence problem

Let

B

be a set with at least

2

elements and

U = {u_{1}, \dots, u_{k}}, V = {v_{1}, \dots, v_{k}} \subset B^{*}

. Does there exist a sequence of indices

i_{1}, \dots, i_{p}

such that

u_{i_{1}} \dots u_{i_{p}} = v_{i_{1}} \dots v_{i_{p}}

Theorem

The Post correspondence problem is recursively undecidable.

Note

Take the sets

U, V

from the Post correspondence problem and define morphisms

τ_{U}, τ_{V} : {[k]}^{*} \to B^{*}

τ_{U} (i) ≔ u_{i}, τ_{V} (i) ≔ v_{i}

. Then the Post correspondence problem can be reformulated as deciding whether

\exists w \in {[k]}^{*} : τ_{U} (w) = τ_{V} (w)

, or equivalently,

{\hat{τ}}_{U} \cap {\hat{τ}}_{V} \neq \emptyset

Note

Let

A = {𝖺, 𝖻}

. Define the injective morphism

κ : {[k]}^{*} \to A^{*}, κ (i) ≔ 𝖺^{i} 𝖻

. Then

\hat{τ_{U} \circ κ^{- 1}} \cap \hat{τ_{V} \circ κ^{- 1}} = \emptyset ⟺ {\hat{τ}}_{U} \cap {\hat{τ}}_{V} = \emptyset .

This somehow implies that the equivalence of rational sets is undecidable.

Theorem

Let

R \subset Rat A^{*} \times B^{*}

with

| A |, | B | \geq 2

. Then it is undecidable whether

R = A^{*} \times B^{*}

\hat{∁ (τ_{U} \circ κ^{- 1})} \cap \hat{∁ (τ_{V} \circ κ^{- 1})} = A^{*} \times B^{*} ⟺ {\hat{τ}}_{U} \cap {\hat{τ}}_{V} = \emptyset .

Note

Let

A \cap B = \emptyset

and

Z ≔ A \cup B

. Define the projections

π_{A} : Z^{*} \to A^{*}, π_{B} : Z^{*} \to B^{*}

the obvious way. Then for a given

θ : A^{*} \to B^{*}

we have

θ \in Rat A^{\times} \times B^{*} ⟺ \exists K \in Rat Z^{*} : θ = π_{B} \circ Z_{K} \circ π_{A}^{- 1} .

Definition

Let

𝒜 = ⟨ Q, I, E, T ⟩, ℬ = ⟨ R, J, F, U ⟩

be two finite automata. A graph-morphism is a function

φ : Q \to R

such that

$φ (I) \subset J,$
$φ (T) \subset U,$
$\forall (p, a, q) \in E : (φ (p), a, φ (q)) \in F .$

We denote

φ : 𝒜 ↬ ℬ

Theorem

φ : 𝒜 ↬ ℬ

, then

| 𝒜 | \subset | ℬ |

Theorem

The projection from

𝒜 \times ℬ

𝒜

is a graph-morphism.

Theorem

φ : 𝒜 ↬ ℬ

, then also

φ : 𝒜^{𝖳} ↬ ℬ^{𝖳}

Definition

A graph-morphism

φ : 𝒜 ↬ ℬ

is conformal if every computation in

ℬ

is the image of a computation in

𝒜

Definition

Given an automaton

𝒜

, denote by

𝒜_{n}

the normalised version of

𝒜

with two new subliminal states

i, t

. A graph-morphism

φ : 𝒜 ↬ ℬ

can be naturally extended to a morphism

φ_{n} : 𝒜_{n} ↬ ℬ_{n}

Definition

The outgoing bouquet of a state

p

in an automaton

𝒜

{Out}_{𝒜} (p) ≔ {e \in E | e = (p, a, q)} .

The ingoing bouquet of a state

q

in an automaton

𝒜

{In}_{𝒜} (q) ≔ {e \in E | e = (p, a, q)} .

Definition

A graph-morphism

φ : 𝒜 ↬ ℬ

is locally outsurjective/outbijective if for all

p \in 𝒜_{n}

, the morphism

φ_{n} : {Out}_{𝒜_{n}} (p) \to {Out}_{ℬ_{n}} (φ (p))

is surjective/bijective.

Definition

Let

𝒜 = ⟨ Q, I, E, T ⟩, ℬ = ⟨ R, J, F, U ⟩

be two finite automata. A morphism from

𝒜

ℬ

is a graph-morphism

φ : 𝒜 ↬ ℬ

which is surjective and locally outsurjective. If there exists a morphism from

𝒜

ℬ

ℬ

is a quotient of

𝒜

Theorem

ℬ

is a quotient of

𝒜

, then

| 𝒜 | = | ℬ |

Definition

A graph-morphism

φ : 𝒜 ↬ ℬ

is locally insurjective/inbijective if for all

p \in 𝒜_{n}

, the morphism

φ_{n} : {In}_{𝒜_{n}} (p) \to {In}_{ℬ_{n}} (φ (p))

is surjective/bijective.

Definition

Let

𝒜 = ⟨ Q, I, E, T ⟩, ℬ = ⟨ R, J, F, U ⟩

be two finite automata. A comorphism from

𝒜

ℬ

is a graph-morphism

φ : 𝒜 ↬ ℬ

which is surjective and locally insurjective. If there exists a comorphism from

𝒜

ℬ

ℬ

is a coquotient of

𝒜

Definition

Let

𝒜 = ⟨ Q, I, E, T ⟩, ℬ = ⟨ R, J, F, U ⟩

be two finite automata. A covering from

𝒜

ℬ

is a graph-morphism

φ : 𝒜 ↬ ℬ

which is surjective and locally outbijective.

Definition

Let

𝒜 = ⟨ Q, I, E, T ⟩, ℬ = ⟨ R, J, F, U ⟩

be two finite automata. A cocovering from

𝒜

ℬ

is a graph-morphism

φ : 𝒜 ↬ ℬ

which is surjective and locally inbijective.

Definition

An automaton

𝒜

is unambiguous if every accepted word has only one computation.

Theorem

φ : 𝒜 \to ℬ

is a morphism, then there exists a subautomaton

𝒞

𝒜

such that

φ : 𝒞 \to ℬ

is a covering.

Definition

A state

q

in a subnormalised transducer

𝒯

is stalled/tape-consistent if, if an ingoing transition is labeled in

{1} \times A

(resp.

A \times {1}

), then all outgoing transitions are labeled in

{1} \times A

(resp.

A \times {1}

Definition

A subnormalised transducer is synchronous if every state is stalled. A relation

θ : A^{*} \to B^{*}

is synchronous if it is realised by a synchronous transducer. The set of synchronous relations is denoted

Syn A^{*} \times B^{*}

Note This corresponds to a Turing machine with two tapes where both tape heads only move forward and simultaneously.

Theorem

The inverse of a synchronous relation is a synchronous relation.

Theorem

The universal relation is synchronous.

Theorem

Syn A^{*} \times B^{*}

is an effective Boolean algebra.

Theorem

A synchronous transducer can be determinised.

Definition

A transducer

𝒯

is homogeneous if for every state

p

, either:

all ingoing transitions of $p$ are in $A^{'} ≔ A^{*} \times {1}$ ( $p$ is of type α), or
all ingoing transitions of $p$ are in $B^{'} ≔ {1} \times B^{*}$ ( $p$ is of type β), or
all ingoing transitions of $p$ are in $C ≔ A^{*} \times B^{*}$ ( $p$ is of type γ).

Theorem

Every synchronous transducer has a homogeneous covering.

Definition

A transducer

𝒯

is complete if:

$𝒯$ is homogeneous,
for every state $p$ of type $γ$ and every $d \in D ≔ A^{'} \cup B^{'} \cup C$ there exists at least one transition out of $p$ labeled by $D$ ,
for every state $p$ of type $α$ (resp. $β$ ) and every $x \in A^{'}$ (resp. $B^{'}$ ) there exists at least one transition out of $p$ labeled by $x$ ,

Theorem

Every homogenous synchronous transducer can be made complete.

Theorem

It is recursively undecidable if a rational relation is synchronous.

Definition

The matrix representation of an automaton

𝒜 = ⟨ Q, I, E, T ⟩

is the morphism

μ : A^{*} \to 𝔹^{Q \times Q}

defined as

{μ (a)}_{p, q} ≔ [p \overset{a}{\to} q] .

We will also represent

I

as a row vector and

T

as a column vector. Then we can write

𝒜 = ⟨ I, μ, T ⟩

Lemma

For every

w \in A^{*}

and

p, q

μ (w) = 1 ⟺ p \to_{𝒜}^{w} q .

L (𝒜) = {w \in 𝒜^{*} | I \cdot μ (w) \cdot T = 1} .

Definition

A language

L \subset A^{*}

is recognisable if there exists a finite monoid

M

, a morphism

α : A^{*} \to M

and

P \subset M

such that

L = α^{- 1} (P)

Theorem

A language is recognisable if and only if it is accepted by a finite automaton.

𝒜 = ⟨ I, μ, T ⟩

2^{{| Q |}^{2}}

Note

An automaton defined on a non-free monoid does not necessarily have a matrix representation because not every function defined on a generating set can be extended to a morphism.

Definition

A finite real-time transducer is a tuple

𝒯 = ⟨ A^{*} \times B^{*}, Q, I, E, T ⟩

, where

Q

is a finite set,

E \subset Q \times (A \times 𝒫 (B^{*})) \times Q

and

I, T : Q \to 𝒫 (B^{*})

. Note that the subsets of

B^{*}

may be infinite!